Wzorzec

Wzorzec

Limit czasowy: 1000 milisekund
Limit pamięciowy: 32000 kilobajtów

Ulubionym zagadnieniem Władka jest problem wyszukiwania wzorca. Przez cały semestr uczęszczania na wykłady z Algorytmów Tekstowych, Władek opracował ponad 10 różnych sposobów rozwiązania tego zadania. Możliwe to było dzięki wykorzystaniu w mniej lub bardziej pokrętny sposób nowo poznanych algorytmów, które nierzadko przeznaczone były do zupełnie innych celów. Niestety, na egzaminie końcowym Władek nie dostał możliwości pochwalenia się nowo nabytą wiedzą - zamiast tego otrzymał następujący problem do rozwiązania: mając dany wzorzec P i tekst T, ile razy dowolnie powiększony P występuje w T?

Wzorzec powiększony k razy, to taki wzorzec w którym każda litera została zastąpiona tą samą literą powtórzoną k razy. Przykładowo, kolejne powiększenia wzorca aabc, to aabc, aaaabbcc, aaaaaabbbccc, aaaaaaaabbbbcccc, itd. Wystąpienie dowolnie powiększonego wzorca P, to takie i, że P powiększony pewną liczbę razy występuje w T począwszy od i-tej litery. Jeżeli więć na pozycji i zaczyna się kilka różnych powiększeń wzorca, to takie wystąpienie liczymy tylko raz (patrz drugi przykład).

Wejście:

W pierwszej linii znajdują się dwie, oddzielone pojedynczym odstępem liczby całkowite n i m (1<=n,m<=1000000). W drugiej linii znajduje się n-elementowy ciąg małych liter alfabetu łacińskiego - jest to tekst T. W trzeciej linii znajduje się m-elementowy ciąg małych liter alfabetu łacińskiego - jest to wzorzec P.

Wyjście:

W pierwszej i jedynej linii Twój program powinien wypisać liczbę wystąpień wzorca w podanym tekście z dowolnym powiększeniem.

Przykład:

Dla danych wejściowych:
6 2
abaabb
ab

poprawną odpowiedzią jest:
3

Wystąpienia wzorca: abaabb, abaabb ,abaabb.

Dla danych wejściowych:
4 1
aaaa
a

poprawną odpowiedzią jest:
4