Podstawowym problemem dotyczącym tekstów jest problem wyszukiwania wzorca. Polega on na znalezieniu wszystkich wystąpień tekstu wzorzec, w tekście tekst. Przyjmujemy ponadto, że: |wzorzec|=m, |tekst|=n oraz n>=m.

Algorytm Galila-Seiferasa umożliwia rozwiązanie tego problemu w czasie liniowym i jednocześnie w pamięcie O(1). Przez pewien czas uważano nawet, że taki algorytm w ogóle nie jest możliwy. Poniżej zostanie opisana jego słabsza wersja.
Na potrzeby tego algorytmu wprowadziwy najpierw pojęcie wzorca łatwego. O wzorcu x powiemy, że jest łatwy, gdy żadne słowo niepuste postaci vvv nie jest jego prefiksem. Na przykład x=bcbcbcdef nie jest ławty, gdyż dla v=bc można zapisać, go jako x=vvvdef, natomiast x=abbababba jest wzorcem łatwym.
W przypadku, gdy mamy do czynienia ze wzorcem ławtym można skonstruować algorytm podobny do algorytmu KMP, w którym tablicę P zastępuje się przez pewne przybliżone oszacowania: P[j]<2j/3, przesunięcie(j)≥j/3

Gotowy algorytm ma postać:
while i<=n-m+1 do
begin
  j:=0;
  while ((j<m)and(wzorzec[j+1]=tekst[i+j])) do j:=j+1;
  if j=m then writeln((IntToStr(i)));
  i:=i+max(1,ceil(j/3));
end;

Algorytm GS' dla wzorców, ktore nie są łatwe, może (choć nie musi) dać odpowiedź niepoprawną. Dla następującego przykładu: wzorzec=aaaaaaab i tekst=aaaaaaaab zostanie wypisanych zero wystąpień wzorca, podczas gdy występuje on w tekscie począwszy od pozycji 2.
Przykładem zbioru łatwych wzorców jest zbiór słów Fibonacciego, który tworzy się podobnie jak ciąg liczb Fibonacciego, z tą jednak różnicą, że zamiast klasycznej sumy liczb stosuje się konkatenację lańcuchów: fib_k+2=fib_k+1fib_k dla k>0. Na przykład dla fib₁=a, fib₂=b otrzymamy kolejno: fib₃=ba, fib₄=bab, fib₅=babba, fib₆=babbbabab.

Komentarze