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.

Algorytm wyszukiwania pierwszego wystąpienia wzorca (metoda naiwna)

Dane wejściowe:
T - tekst, w którym szukamy wzorca,
W - tekst, będący wzorcem, którego szukamy
Wynik: indeks elementu, od którego rozpoczyna się pierwsze wystąpienie wzorca w tekście lub komunikat „BRAK” jeśli wzorzec nie występuje.

Lista kroków:

Ustal długości: 
n – długość tekstu T, 
m – długość wzorca W.
Ustaw pozycję początkową i = 0.
Dopóki i ≤ n - m:
	Porównuj kolejno znaki wzorca W z odpowiadającymi im znakami tekstu T od pozycji i.
    	Jeśli wszystkie znaki się zgadzają → zwróć indeks i (to pierwsze wystąpienie wzorca).
        Zakończ program
    	W przeciwnym razie przesuń się o jedno miejsce w prawo (i = i + 1).
Jeśli po sprawdzeniu wszystkich możliwych pozycji nie znaleziono dopasowania, zwróć komunikat: "brak wzorca w tekście".

Przykład działania:

Tekst: T = „ababcababc”
Wzorzec: W = „abc”
n = 10
m = 3
Porównuje „abc” z T[0..2] → nie pasuje
Porównuje „abc” z T[1..3] → nie pasuje
Porównuje „abc” z T[2..4] → pasuje 

Wynik: pierwsze wystąpienie na pozycji 2