BUK 2002 - 2. Zadanie domowe, wyszukiwanie wielu wzorców

2002-01-01

Zadanie

Napisz program który:
  • wczyta ze standardowego wejścia (stdin) listę wzorców oraz tekst
  • wypisze na standardowe wyjscie pozycje w tekście na których występowały wzorce.

uproszczenie:

  • żadne dwa wzorce ze zbioru nie są swoimi podsłowami (np. nie są możliwe wzorce: abaxyz, bax, czy: abaxyz, aba)

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą k (1<=k<=100). W kolejnych k wierszach zapisane sa wzorce (po jednym w kazdym wierszu), każdy wzorzec składa się z liter a-z. W k+2 linii znajduje się liczba n – długość tekstu (1<n<1000000). W k+3 zapisany jest tekst.

Wyjście

Program powinien zapisać na standardowe wyjście uporządkowane rosnąco pozycje na których wystąpił pewien wzorzec z listy (przez pozycję należy rozumieć, indeks pierwszej litery w wystąpieniu). Każde wystąpienie powinno zostać zapisane w osobnym wierszu.

Przykład

Dla danych:

3
abb
aaa
aba
14
aaababbbabbaaa

prawidłową odpowiedzią jest

1
3
5
9
12

Ocenianie

  • wymagane jest nadesłanie źródła i kompilatu na adres: walen@mimuw.edu.pl do dnia 10.04.2002.
  • języki programowania: C/C++/Pascal/Java
  • liczba punktów: 25 -- poprawne rozwiązanie o złożoności O(n+m)
  • liczba punktów: 5 -- poprawne rozwiązanie o złożoności O(nm)

Literatura

Tomasz Waleń
Tomasz Waleń
Assistant Professor