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:

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