| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
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łowego | 50000B |
| 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 |