시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

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).

입력

W pierwszej linii znajdują się dwie, oddzielone pojedynczym odstępem liczby całkowite 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.

출력

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

예제 입력 1

6 2
abaabb
ab

예제 출력 1

3

Wystąpienia wzorca: abaabb, abaabb ,abaabb.

예제 입력 2

4 1
aaaa
a

예제 출력 2

4