Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KMP - Wyszukiwanie wzorca w tekscie

Napisz program, który dla danego wzorca P (ang. pattern) i tekstu T wypisze pozycje, na których znajduje się wzorzec P jako podsłowo tekstu T.

Wejście

W pierwszym wierszu danych znajduje się liczba natralna T (0 < T < 11) oznaczająca liczbę zestawów danych.
Każdy zestaw danych podany jest w trzech wierszach. Pierwszy zawiera jedną liczbę naturalną n - oznaczającą długość wzorca P ( n <= 1000000 ). Drugi wiersz zawiera wzorzec P - napis złożony z n liter angielskiego alfabetu (a-z, A-Z). Trzeci wiersz zawiera test T czyli ciąg liter alfabetu angielskiego zakończony znakiem nowego wiersza.

Wyjście

Dla każdego zestawu danych wypisz pozycje na których wzorzec P pasuje w tekscie T. Zakładamy, że litery tekstu T numerowane są od zera.

Przykład

Wejście:
3
2
na
banananobano
6
foobar
foo
9
foobarfoo
barfoobarfoobarfoobarfoobarfoo


Wyjście
2
4
3
9
15
21

Dodane przez:Rafal Nowak
Data dodania:2007-01-14
Limit czasu wykonania programu:1s-2.313s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ADA95 ASM32 BASH BF CSHARP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN GOSU HASK ICON ICK JAVA JS-RHINO LUA NEM NICE OCAML PAS-GPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE
Pochodzenie:Klasyka
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.