Jak odnaleźć wzorzec w tekście?

Rozważmy następujący problem. Mamy ciąg znaków: jedno słowo (np. „kot”) lub kilka wyrazów – np. zdanie „ala ma kota” (dla uproszczenia pomijamy wielkości liter). Problem wyszukania wzorca w tekście polega na odnalezieniu takiej liczby, która określa, ile początkowych znaków tekstu należy usunąć, aby rozpoczynał się on właśnie od wzorca. W przytoczonym przykładzie taką cyfrą będzie 7. Po usunięciu z ciągu „ala ma kota” 7 początkowych znaków, zostaniemy z wyrażeniem „kota”. Wówczas łatwo zauważyć, że wzorzec „kot” pasuje do początku zdania.

W jaki sposób odbywa się szukanie wzorca w tekście? Pomocna jest tzw. metoda naiwna, określana często mianem brute forcebrute forcebrute force. Polega ona na wykonywaniu porównania wzorca z początkiem tekstu dla każdej liczby znaków, które z niego usuniemy. Takie wyszukiwanie w podanym przykładzie będzie wyglądało następująco:

R1PPQUTSZhpVo

Ilustracja przedstawia szukanie wzorca słowa: kot, w zdaniu: ala ma kota.
Na samej górze umieszczono zdanie: ala ma kota.
Poniżej znajduje się 10 linii gdzie słowo: kot przesuwane jest o jedną literę względem zdania.
W liniach od 1 do 7 nie znaleziono wzorca i literka k podświetla się na czerwono.
W linii ósmej literka k słowa kot wyrównało się z literka k ze zdania i podświetla się na zielono.
W linii 9 na zielono podświetla się litera: o, a w linii 10: t.

Podstawową wadą tej metody jest to, że nie jest ona optymalna. Nie nadaje się do poszukiwania długich wzorców w długich tekstach. Istnieją algorytmy, które dużo efektywniej radzą sobie w podobnych sytuacjach. Jednym z takich algorytmów jest algorytm Knutha‑Morrisa‑Pratta.

Wstęp do algorytmu Knutha‑Morrisa‑Pratta

Algorytm ten jest pierwszym odkrytym algorytmem, który rozwiązuje problem wyszukiwania wzorca w tekście, cechuje się złożonością liniową względem długości tekstu oraz wzorca. Jego nazwa pochodzi od trzech matematyków‑informatyków, którzy wspólnie opublikowali ostateczną wersję algorymtu: Donald Ervin Knuth, Vaughan Ronald Pratt oraz James Hiram Morris. W skrócie algorytm nazywamy „KMP”.

Algorytm KMP sprawdza po kolei każdy znak tekstu, do którego możemy dopasować wzorzec. W momencie, gdy pierwszy znak wzorca oraz aktualnie przetwarzany znak tekstu są takie same, rozpoczynamy sprawdzanie po kolei, czy następne znaki wzorca i tekstu są identyczne. Na pierwszy rzut oka metoda ta działa w taki sam sposób, jak metoda naiwna. Usprawnienie pojawia się jednak w momencie, gdy już znaleźliśmy potencjalne dopasowanie, które okazuje się błędne. W takiej sytuacji algorytm KMP pomija sprawdzanie dopasowania na tych następnych pozycjach, które na pewno okażą się błędne.

Pomocna w tym działaniu jest analiza wstępna wzorca, która polega na utworzeniu tablicy częściowych dopasowań. Przechowuje ona liczby całkowite. Długość takiej tablicy to długość wzorca powiększona o 1. Aby najłatwiej wytłumaczyć proces analizy wzorca w algorytmie KMP, posłużymy się wcześniejszą jego wersją (znaną jako algorytm MP), a następnie rozszerzymy ją o pewien dodatkowy przypadek, dzięki któremu powstała jego obecna wersja.

Chcąc dokładnie omówić tę procedurę, musimy wprowadzić kilka pojęć:

1. prefiks – składająca się z k znaków przednia część łańcucha znaków;

2. sufiks – składająca się z k znaków końcowa część łańcucha znaków;

3. prefikso‑sufiks – składająca się z k znaków część łańcucha znaków, która występuje zarówno z przodu, jak i z tyłu;

4. szerokość prefikso‑sufiksu – długość prefiksu lub sufiksu, z którego składa się prefikso‑sufiks.

Budowa tablicy częściowych dopasowań w algorytmie MP polega na wyznaczeniu maksymalnego prefikso‑sufiksu dla każdego możliwego prefiksu we wzorcu.

Oznaczmy ciąg znaków wzorzec jako W oraz tablicę częściowych dopasowań jako T.

Krok 0:

Na zerowej pozycji w tablicy T wstawimy liczbę -1, która będzie naszym wartownikiemwartownikwartownikiem.

RrnePchYkQS1U

Ilustracja przedstawia tabelę z dwoma wierszami.
Wiersz pierwszym: W, puste, G, C, A, T, G, C, G, A ,G ,C.
W drugim wierszu kolejno: T, -1, reszta pól jest pusta.

Krok 1:

Pierwszy możliwy prefiks wzorca to „G”. Wśród ciągu znaków „G” nie występuje żaden prefikso‑sufiks, zatem kolejny element w tablicy T to 0 – prefikso‑sufiks pusty.

RgRUBIjKyXWzY

Ilustracja przedstawia tabelę z dwoma wierszami.
Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole trzecie z literą G zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0 reszta pól jest pusta.

Krok 2:

Kolejny prefiks wzorca to „GC”. Nie występuje żaden prefikso‑sufiks, zatem jako kolejny element tablicy również wstawiamy 0 – prefikso‑sufiks pusty.

RIpcZTx3g8Zpp

Ilustracja przedstawia tabelę z dwoma wierszami.
Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole trzecie i czwarte z kolejnymi literami: G, C zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0 reszta pól jest pusta.

Krok 3:

Kolejny prefiks to „GCA”. Znowu występuje jedynie prefikso‑sufiks pusty, więc do tablicy wstawiamy 0.

R1HiZ7YFxEf1o

Ilustracja przedstawia tabelę z dwoma wierszami.
Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola od trzeciego do piątego z kolejnymi literami: G, C, A zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0 reszta pól jest pusta.

Krok 4:

Sytuacja jak poprzednio – wstawiamy 0.

RU4ba4ra2pSPX

Ilustracja przedstawia tabelę z dwoma wierszami.
Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola od trzeciego do szóstego z kolejnymi literami: G, C, A, T zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, 0 reszta pól jest pusta.

Krok 5:

W aktualnie przeszukiwanym fiksie „GCATG” znaleźliśmy pierwszy prefikso‑sufiks. Jego szerokość wynosi 1, zatem w tablicy umieszczamy element 1.

RacgQ4oKNc0fO

Ilustracja przedstawia tabelę z dwoma wierszami.
Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola trzecie i siódme zawierające literę G zaznaczono kolorem zielonym, pola od czwartego do szóstego z kolejnymi literami: C, A, T zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, 0, 1 reszta pól jest pusta.

Krok 6:

W kolejnym prefiksie największy prefikso‑sufiks, jaki znajdziemy, jest o szerokości 2. Zauważmy, że nie musimy w tym kroku przeszukiwać całego prefiksu „GCATGC”, gdyż możemy kontynuować wyszukiwanie, które rozpoczęliśmy w poprzednim kroku.

RBReEkZM4CYou

Ilustracja przedstawia tabelę z dwoma wierszami.
Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola trzecie, siódme zawierające literę G, pola czwarte i ósme zawierają literą C, zaznaczono je kolorem zielonym, pola piąte i szóste z kolejnymi literami: A, T zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, 0, 1, 2 reszta pól jest pusta.

Krok 7:

W tym kroku największy prefikso‑sufiks ma szerokość 1. Pamiętając o informacji z poprzedniego kroku, sprawdź czy uda się rozszerzyć poprzednio znaleziony prefikso‑sufiks. Dopiero gdy próba się nie powiedzie, sprawdzamy, czy możemy znaleźć inny prefikso‑sufiks. Zatem w tym kroku są wykonywane tak naprawdę 2 kroki.

RZgJ9fLy6nTDh

Ilustracja przedstawia tabelę z dwoma wierszami.
Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola trzecie i dziewiąte zawierające literę G zaznaczono kolorem zielonym, pola od czwartego do ósmego z kolejnymi literami: C, A, T, G, C zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, 0, 1, 2, 1 reszta pól jest pusta.

Krok 8:

W prefiksie „GCATGCGA” nie ma żadnego prefikso‑sufiksu. Również w tym kroku próbowaliśmy rozszerzyć poprzedni prefikso‑sufiks.

RILM3Vla4JLcB

Ilustracja przedstawia tabelę z dwoma wierszami.
Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola od trzeciego do dziesiątego z kolejnymi literami: G, C, A, T, G, C, G, A zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, 0, 1, 2, 1, 0 reszta pól jest pusta.

Krok 9:

Znaleźliśmy prefikso‑sufiks o długości 1 – w tablicy zapisujemy tę wartość.

R1MC5MFyqyWtP

Ilustracja przedstawia tabelę z dwoma wierszami.
Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola trzecie i jedenaste zawierające literę G zaznaczono kolorem zielonym, pola od czwartego do dziesiątego z kolejnymi literami: C, A, T, G, C, G, A zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, 0, 1, 2, 1, 0, 1 reszta pól jest pusta.

Krok 10:

Możemy rozszerzyć poprzednio znaleziony prefikso‑sufiks. Do tablicy wpisujemy wartość o 1 większą niż w poprzednim kroku.

R1GnQT1SkIlHV

Ilustracja przedstawia tabelę z dwoma wierszami.
Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola trzecie i jedenaste zawierające literę G, a pola czwarte i dwunaste literę: C.
Pola te zaznaczono kolorem zielonym, pola od piątego do dziesiątego z kolejnymi literami: C, A, T, G, C, G, A zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, 0, 1, 2, 1, 0, 1, 2.

Wszystkie powyżej opisane kroki możemy przedstawić za pomocą poniższego pseudokodu. Jako W oznaczono wzorzec:

funkcja budowaTablicyMP(W)
    rozmiarT = długość(W) + 1
   	stwórz tablicę T o długości rozmiarT
    poz = -1
    T[0] = -1

	// dla każdego kolejnego prefiksu wzorca
    dla i = 1, 2, ..., rozmiarT - 1 wykonuj:
    	// dopóki możesz znaleźć dłuższy prefikso-sufiks
        dopóki poz > -1 i W[poz] != W[i - 1] wykonuj:
            poz = T[poz]
        poz += 1

		// zapisz szerokość znalezionego prefikso-sufiksu
        T[i] = poz

    zwróć T

Usprawnienie

Omówmy dodatkowy, wspominany już przypadek, który ulepsza metodę MP do KMP. Występuje wówczas, gdy znaleźliśmy prefikso‑sufiks (może być pusty) w aktualnie sprawdzanym prefiksie, ale znak następujący po tym prefiksie, jest taki sam jak ten, który występuje po prefikso‑sufiksie (po części prefiksowej). W takiej sytuacji do tablicy wstawiamy wartość, która już została zapisana w tablicy T na pozycji określonej długością obecnego prefikso‑sufiksu. Jeżeli porównywane elementy są różne, do tablicy wpisujemy długość prefikso‑sufiksu. Brzmi to bardzo skomplikowanie. Dlatego też prześledźmy to na konkretnym przykładzie – tym samym, który omówiliśmy przy algorytmie MP.

Krok 0:

Tak jak w przypadku algorytmu MP, na zerowym miejscu tablicy wstawiamy wartownika -1.

RzUoGZ1kXsicH

Ilustracja przedstawia tabelę z dwoma wierszami.
Wiersz pierwszym: W, puste, G, C, A, T, G, C, G, A ,G ,C.
W drugim wierszu kolejno: T, -1, reszta pól jest pusta.

Krok 1:

Jedyny prefikso‑sufiks, który jesteśmy w stanie znaleźć, to prefikso‑sufiks pusty. Należy jednak porównać zaznaczone na niebiesko elementy (element występujący po znalezionym prefikso‑sufiksie – „G”) oraz element występujący po aktualnie przetwarzanym prefiksie – „C”). Są różne, zatem możemy wpisać do tablicy szerokość znalezionego prefikso‑sufiksu – 0.

R1b1ewZxUERcB

Ilustracja przedstawia dwie tabelę z dwoma wierszami.
Tabela pierwsza: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole trzecie z literą G zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, reszta pól jest pusta.
Tabela druga: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole trzecie i czwarte z literami G, C zaznaczono kolorem granatowym.
W drugim wierszu kolejno: T, -1, 0 reszta pól jest pusta.

Krok 2:

Podobna sytuacja jak w kroku 1. Znaleźliśmy prefikso‑sufiks pusty. Porównujemy 2 elementy, które występują po znalezionym prefikso‑sufiksie oraz po przetwarzanej części wzorca. Są one różne, zatem możemy wstawić szerokość prefikso‑sufiksu.

R7n66dD3FHgEC

Ilustracja przedstawia dwie tabelę z dwoma wierszami.
Tabela pierwsza: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola trzecie i czwarte z literami G, C zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0 reszta pól jest pusta.
Tabela druga: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole trzecie i piąte z literami G, A zaznaczono kolorem granatowym.
W drugim wierszu kolejno: T, -1, 0, 0 reszta pól jest pusta.

Krok 3:

Sytuacja identyczna jak w poprzednim kroku – wstawiamy 0.

R1Ndp9m3HUT0c

Ilustracja przedstawia dwie tabelę z dwoma wierszami.
Tabela pierwsza: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola od trzeciego do piątego z literami G, C, A zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0 reszta pól jest pusta.
Tabela druga: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole trzecie i szóste z literami G, T zaznaczono kolorem granatowym.
W drugim wierszu kolejno: T, -1, 0, 0, 0 reszta pól jest pusta.

Krok 4:

Znowu znaleźliśmy pusty prefikso‑sufiks. Jest to jednak pierwszy przypadek, w którym porównywane później elementy są takie same. W takiej sytuacji musimy odczytać z tablicy T wartość pod indeksem określonym przez długość obecnego prefikso‑sufiksu. Długość ta wynosi w tym wypadku 0 (prefikso‑sufiks pusty), T[0] = -1, zatem ustawiamy wartownika -1.

R8TvOk4GdVwej

Ilustracja przedstawia dwie tabelę z dwoma wierszami.
Tabela pierwsza: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola od trzeciego do szóstego z literami G, C, A, T zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0 reszta pól jest pusta.
Tabela druga: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole trzecie i siódme z literami G, G zaznaczono kolorem granatowym.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, reszta pól jest pusta.

Krok 5:

Znaleźliśmy prefikso‑sufiks o szerokości 1. Elementy, które musimy porównać, są takie same, zatem odczytujemy T[1] = 0, wpisujemy 0.

R11veRqkEJC8u

Ilustracja przedstawia dwie tabelę z dwoma wierszami.
Tabela pierwsza: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola trzecie i siódme z literami G, G zaznaczono kolorem zielonym, od czwartego do szóstego z literami C, A, T zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, reszta pól jest pusta.
Tabela druga: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole czwarte i ósme z literami C, C zaznaczono kolorem granatowym.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, 0, reszta pól jest pusta.

Krok 6:

Prefikso‑sufiks ma szerokość 2. Ponieważ elementy „A” i „G” są różne, szerokość wpisujemy do tablicy.

R1B0eTw1CCmlq

Ilustracja przedstawia dwie tabelę z dwoma wierszami.
Tabela pierwsza: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola trzecie i siódme z literami G, G, czwarte i ósme z literami C, C zaznaczono kolorem zielonym, od piątego do szóstego z literami A, T zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, 0 , reszta pól jest pusta.
Tabela druga: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole piąte i dziewiąte z literami A, G zaznaczono kolorem granatowym.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, 0, 2. reszta pól jest pusta.

Krok 7:

W tym kroku znaleziony prefikso‑sufiks ma szerokość 1, elementy, które porównujemy są różne, więc do tablicy wstawiamy 1.

R1C3Zs44Ib4kN

Ilustracja przedstawia dwie tabelę z dwoma wierszami.
Tabela pierwsza: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola trzecie i dziewiąte, z literami G, G, zaznaczono kolorem zielonym, od czwartego do ósmego z literami C, A, T, G, C zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, 0 , 2, reszta pól jest pusta.
Tabela druga: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole czwarte i dziesiąte z literami C, A zaznaczono kolorem granatowym.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, 0, 2, 1. reszta pól jest pusta.

Krok 8:

Prefikso‑sufiks jest pusty – szerokość 0. Następny element tablicy będzie zatem równy elementowy T[0], czyli -1.

RmVc8QKbm7sBU

Ilustracja przedstawia dwie tabelę z dwoma wierszami.
Tabela pierwsza: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola od trzeciego do dziesiątego zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, 0 , 2, 1, reszta pól jest pusta.
Tabela druga: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole trzecie i jedenaste z literami G, G zaznaczono kolorem granatowym.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, 0, 2, 1, -1. reszta pól jest pusta.

Krok 9:

Udało się rozszerzyć znaleziony w poprzednim kroku prefikso‑sufiks pusty do szerokości 1. Porównywane elementy są takie same, zatem wstawiamy wartość z komórki o indeksie równym szerokości. T[1] = 0, więc kolejnym elementem będzie 0.

RWFr7HrkAitzk

Ilustracja przedstawia dwie tabelę z dwoma wierszami.
Tabela pierwsza: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola trzecie i jedenaste, z literami G, G, zaznaczono kolorem zielonym, od czwartego do dziesiątego z literami C, A, T, G, C, G, A zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, 0 , 2, 1, -1. reszta pól jest pusta.
Tabela druga: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole czwarte i dwunaste z literami C, C zaznaczono kolorem granatowym.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, 0, 2, 1, -1, 0. reszta pól jest pusta.

Krok 10:

Szerokość znalezionego prefikso‑sufiksu to 2. Jako że osiągnęliśmy koniec wzorca i nie mamy z czym porównać elementu „A”, możemy założyć, że zawsze jest on inny od elementu, z którym byśmy go porównywali. W rzeczywistości algorytm sprawdza moment, w którym dochodzimy do końca wzorca. W takiej sytuacji do tablicy wstawiamy szerokość prefikso‑sufiksu.

R1YYdNUvIqzfn

Ilustracja przedstawia dwie tabelę z dwoma wierszami.
Tabela pierwsza: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pola trzecie i jedenaste, z literami G, G oraz pola czwarte i dwunaste z literami C, C zaznaczono kolorem zielonym, od piątego do dziesiątego z literami A, T, G, C ,G, A zaznaczono kolorem morskim.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, 0 , 2, 1, -1, 0 reszta pól jest pusta.
Tabela druga: Wiersz pierwszy: W, puste, G, C, A, T, G, C, G, A ,G ,C.
Pole piąte z literą, A zaznaczono kolorem granatowym.
W drugim wierszu kolejno: T, -1, 0, 0, 0, -1, 0, 2, 1, -1, 0, 2.

Ostateczny algorytm może być zapisany za pomocą następującego pseudokodu. Jako W oznaczono wzorzec, T to tablica częściowych dopasowań. Zwróćmy uwagę, że różni się od metody MP tylko jedną dodatkową konstrukcją warunkową.

funkcja budowaTablicyKMP(W)
    rozmiarT = długość(W) + 1
    stwórz tablicę T o długości rozmiarT
    poz = -1
    T[0] = -1

	// dla każdego kolejnego prefiksu wzorca
    dla i = 1, 2, ..., rozmiarT - 1 wykonuj:
    	// dopóki możesz znaleźć dłuższy prefikso-sufiks
        dopóki poz > -1 i W[poz] != W[i - 1] wykonuj:
            poz = T[poz]
        poz += 1

		// usprawnienie
        
        // jeżeli element występujący po znalezionym 
        // prefikso-sufiksie jest taki sam jak po prefiksie
		jeżeli i == rozmiarT - 1 LUB W[i] != W[poz]
        	// zapisz szerokość znalezionego prefikso-sufiksu
            T[i] = poz
        w przeciwnym wypadku
        	// kolejny element tablicy będzie tym samym,
            // co element na pozycji równej szerokości
            // prefikso-sufiksu
            T[i] = T[poz]

    zwróć T

Wykorzystanie tablicy częściowych dopasowań

Dlaczego budujemy tablicę częściowych dopasowań? Wyobraźmy sobie prosty przykład, w którym metodą naiwną próbujemy znaleźć dopasowanie wzorca (AAB) w tekście (AAAAAAB). Dopasowania zaznaczamy na zielono. Czerwonym kolorem oznaczamy te próby, które kończą się niepowodzeniem.

R1Tz3dbWp8KYW

Ilustracja przedstawia szukanie wzorca : AAB, w ciągu liter: AAAAAAB.
Na samej górze umieszczono ciąg liter: AAAAAAB.
Poniżej znajduje się 15 linii gdzie: AAB przesuwane jest o jedną literę względem AAAAAAB.
W linii pierwszej: A podświetlone jest na zielono.

W linii drugiej: drugie A podświetlone jest na zielono.
W linii trzeciej: B podświetlone jest na czerwono.
W linii czwartej: A podświetlone jest na zielono.
W linii piątej: drugie A podświetlone jest na zielono.
W linii szóstej: B podświetlone jest na czerwono.
W linii siódmej: A podświetlone jest na zielono.
W linii ósmej: drugie A podświetlone jest na zielono.
W linii dziewiątej: B podświetlone jest na czerwono.
W linii dziesiątej: A podświetlone jest na zielono.
W linii jedenastej: drugie A podświetlone jest na zielono.
W linii dwunastej: B podświetlone jest na czerwono.
W linii trzynastej: A podświetlone jest na zielono.
W linii czternastej: drugie A podświetlone jest na zielono.
W linii piętnastej: B podświetlone jest na zielono.

Już po pierwszej próbie dopasowania widoczne jest, że kolejną próbę dopasowania możemy rozpocząć, pomijając sprawdzenie pierwszego znaku. Wiemy bowiem, że drugi znak jest taki sam jak pierwszy, a drugi w tym miejscu już pasował. Optymalne dopasowywanie wyglądałoby w następujący sposób:

R1I5GNluWq20I

Ilustracja przedstawia szukanie wzorca : AAB, w ciągu liter: AAAAAAB.
Na samej górze umieszczono ciąg liter: AAAAAAB.
Poniżej znajduje się 11 linii gdzie: AAB przesuwane jest o jedną literę względem AAAAAAB.
W linii pierwszej: A podświetlone jest na zielono.

W linii drugiej: drugie A podświetlone jest na zielono.
W linii trzeciej: B podświetlone jest na czerwono.
W linii czwartej: drugie A podświetlone jest na zielono.
W linii piątej: B podświetlone jest na czerwono.
W linii szóstej: drugie A podświetlone jest na zielono.
W linii siódmej: B podświetlone jest na czerwono.
W linii ósmej: drugie A podświetlone jest na zielono.
W linii dziewiątej: B podświetlone jest na czerwono.
W linii dziesiątej: drugie A podświetlone jest na zielono.
W linii jedenastej: B podświetlone jest na zielono.

Porównując inteligentne przeszukiwanie z metodą naiwną, zaoszczędziliśmy cztery porównania. Być może nie jest to dużo, jednak różnica zwiększa się wraz ze wzrostem długości tekstu oraz wzorca.

Algorytm wyszukiwania wzorca w tekście z wykorzystaniem tablicy dopasowań wygląda następująco. Warto zaznaczyć, że działa on zarówno dla tablicy dopasowań metody MP, jak i KMP, jednak tablica znaleziona algorytmem KMP jest po prostu bardziej wydajna. Jako W oznaczono wzorzec, a jako S – przeszukiwany tekst.

funkcja szukajAlgorytmemKMP(W, S)
    T = budowaTablicyKMP(W)
    b = 0
    dla i = 0, 1, ..., długość(S) - 1 wykonuj:
        dopóki b > -1 i W[b] != S[i] wykonuj:
            b = T[b]
        b += 1
        jeżeli b == długość(W):
            zwróć i - długość(W) + 1
    zwróć -1

Słownik