Polish version    English version  
 


 News
 About Olympic
 History of OI
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
This document is not available in English version.

III Obóz im. A. Kreczmara 2002

Zadanie: d
Autor: Piotr Sankowski
D: Literowe permutacje tekstów

dzień czwarty 9 sierpnia 2002
Plik źródłowy: d.??? (np. pas, c, cpp)
Plik wejściowy: d.in
Plik wyjściowy: d.out

Permutacja liter to przypisanie literom liter w taki sposób, aby każdej literze była przypisana inna litera. Literową permutacją tekstu nazywamy tekst powstały poprzez zamianę liter w wejściowym tekście zgodnie z pewną permutacją liter. Twoim zadaniem jest znalezienie liczby wystąpień literowych permutacji zadanego wzorca w zadanym tekście. Permutacje liter zawierają wszystkie małe litery alfabetu angielskiego.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego d.in tekst i wzorzec,
  • policzy, ile razy permutacje literowe wzorca występują w tekście,
  • zapisze do pliku wynikowego d.out liczbę wystąpień permutacji literowych wzorca w tekście.

Wejście

W pierwszym wierszu pliku tekstowego d.in znajdują się dwie liczby całkowite n i m oddzielone spacją (1 <= n <= 1000000; 1 <= m <= 1000), oznaczające odpowiednio długość tekstu i długość wzorca. W kolejnym wierszu zapisanych jest n małych angielskich liter nieoddzielonych spacjami. Jest to tekst. W następnym wierszu zapisanych jest m małych angielskich liter nieoddzielonych spacjami. Jest to wzorzec.

Wyjście

Plik tekstowy d.out powinien zawierać jedną liczbę całkowitą będącą liczbą wystąpień permutacji literowych wzorca w tekście.

Przykład

Dla pliku wejściowego d.in:

8 4
aabbaabb
aabb

poprawną odpowiedzią jest plik wyjściowy d.out:

3



Print friendly version