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.

Co to jest metoda naiwna?

Metoda naiwna polega na sprawdzaniu każdego możliwego miejsca w tekście, w którym wzorzec mógłby się zaczynać, i porównywaniu znak po znaku, czy wzorzec pasuje do fragmentu tekstu.

Nie jest to algorytm szczególnie wydajny, ale jego prostota sprawia, że jest idealnym punktem wyjścia do nauki bardziej zaawansowanych technik.

Idea działania

Załóżmy, że mamy tekst T o długości n i wzorzec P o długości m. Algorytm:

1. Przesuwa wzorzec od początku tekstu aż do pozycji n - m.

2. Na każdej pozycji sprawdza, czy znaki wzorca pasują do odpowiadających znaków tekstu.

3. Jeśli wszystkie znaki pasują – mamy dopasowanie.

4. Jeśli choć jeden znak się różni – przesuwamy wzorzec o jedną pozycję dalej.

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