Algorytm KMP

ALGORYTM KMP
Przeszukiwanie tekstów
Problemem, który często się pojawia w różnych zagadnieniach jest problem wyszukiwania wzorca, który polega na znajdowaniu wszystkich wystąpień danego wzorca w tekście.

Zakładamy ,że tekst przeszukiwany jest tablicą T[1…n] długości n, a wzorzec
tablicą W[1…m] długości m. Ponadto zakładamy, że elementy tablic W i T należą do pewnego skończonego alfabetu, może nim być np. alfabet łaciński, albo dwuznakowy(0 i 1).

Dość łatwo znaleźć algorytm brutalny wyszukiwania tekstu w celu znalezienia w nim wzorca. Wzorzec traktujemy jako „okienko”, które przesuwamy wzdłuż badanego tekstu. Trzymamy indeksy i oraz j, które aktualnie znaki porównujemy w tekście i we wzorcu. Dopóki porównywane elementy są jednakowe, zwiększamy obydwa indeksy. Jednakże, gdy pojawi się niezgodność znaków musimy zacząć wszystko od nowa dla kolejnej literki w tekście.
W pseudokodzie wygląda to następująco:

Naive-Strong-Matcher(T,W)
1.    n-długość słowa T
2.    m-długość wzorca W
3.    j=i=0;
4.    while(j<m && i<n)
5.        if(T[i]!=W[j])
6.            i=i-(j-1);
7.                  j=-1;
8.            i++;j++;
9.        if(j==m)
10.               wypisz pozycje
11.            i=i-(j-1);
12.            j=-1;
13.            i++;j++;

Linie 11-13 są po to, aby program się nie głupiał jak znajdzie jeden wzorzec, tylko podjął dalej swój obowiązek.

Powyższy algorytm jest dość wolny. Jego złożoność może wynieść O(n²), jeżeli większa część wzorca będzie występować wiele razy w tekście.
Przykładowo jak wyszukujemy aaaa w ciągu aaabaabaaab, prawie za każdym razem dopasujemy kilka znaków, ale ani razu całego wzorca.

Czasami po niedopasowaniu wzorca można przeskoczyć więcej niż jeden znak.
Przykładowo, jeżeli początek danej części wzorca, którą już dopasowaliśmy jest taki sam jak jej koniec,

Zacznijmy od określenie kilku pojęć:
Najdłuższy prefikso-sufiks słowa: jest to najdłuższy prefiks, będący jednocześnie sufiksem słowa, a nie będący tym słowem (czyli słowo nie jest swoim prefikso-sufiksem).
|W|- długość słowa W
KMP[1….n]- tablica określająca rozmiar prefikso-sufiksu dla T[1….n].

W algorytmie brutalnym cofamy się o całą długość wzorca w razie niedopasowania, zapominając wszystko co przetestowaliśmy do tej pory.
W przypadku KMP będziemy przeskakiwać trochę więcej niż o 1 znak.

KMP-Matcher(T,W)
1.    n-długość słowa T
2.    m-długość wzorca W
3.    while(i<n-m)
4.        j=KMP[j];
5.        while ((j<m)&&(W[j+1]==T[i+j])) j+=1;
6.        if(j==m) 
7.            wypisz pozycje
8.        i+=max(1,j-KMP[j]);

A jak policzyć tą tablicę KMP?
Niech KMP dla 0 i 1 niech będzie 0.
Tak jak w programowaniu dynamicznym będą potrzebne nam poprzednie obliczenia.

Trzeba zaimplementować te 2 przypadki.
Kod jest dość krótki:

Make_KMP(W)
1.    KMP[0]=KMP[1]=t=0;
2.    for j=2 to m do
3.        while ((t>0)&&(W[t+1]!=W[j])) t=KMP[t];
4.        if(W[t+1]==W[j])t+=1;
5.        P[j]=t;

Można wyszukiwać inaczej:
połączyć (konkatenacja czy jakoś inaczej:| ) wzorzec z Tekstem.
To jest połączenie bez żadnych dodatkowych znaków.
I teraz sobie liczymy KMP dla takiego długiego ciągu(nazwijmy to od teraz Wzorcem).
Zwracam uwagę na wielkość liter: Wzorzec=wzorzec+Tekst
Jeżeli dla jakiegoś podciągu Wzorca KMP przekroczy długość wzorca, to pozostaje tylko wypisać aktualną pozycję-długość wzorca.

Problem równoważności cyklicznej:
Co to jest to można przeczytać w zadaniu gamma.
Jak to zrobić?
Wystarczy skleić jeden łańcuch A dwukrotnie, powstanie AA
I trzeba wyszukać B w AA, oraz odwrócony B w AA.