III Obóz im. A. Kreczmara 2002
|
Zadanie: d
|
Autor: Piotr Sankowski
|
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.
Napisz program, który:
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.
Plik tekstowy d.out powinien zawierać jedną liczbę całkowitą będącą liczbą wystąpień permutacji literowych wzorca w tekście.
Dla pliku wejściowego d.in:
8 4 aabbaabb aabb
poprawną odpowiedzią jest plik wyjściowy d.out:
3