Wyszukiwanie wzorca w tekscie.

Problem

W łańcuchu znakowym s znaleźć wszystkie wystąpienia wzorca p.

Rozwiązanie

Problem Wyszukiwania Wzorca – WW (ang. pattern matching) to jeden z podstawowych problemów tekstowych, który intensywnie badali wybitni informatycy. Rozwiązaniem jest wskazanie w ciągu s wszystkich pozycji i takich, że zachodzi równość:

s[i : i + |p|] = p

Oznacza to, iż wzorzec p jest fragmentem łańcucha s występującym na pozycji i-tej.

Algorytm N – naiwny – ustawia okno o długości wzorca p na pierwszej pozycji w łańcuchu s. Następnie sprawdza, czy zawartość tego okna jest równa wzorcowi p. Jeśli tak, pozycja okna jest zwracana jako wynik, po czym okno przesuwa się o jedną pozycję w prawo i cała procedura powtarza się. Algorytm kończymy, gdy okno wyjdzie poza koniec łańcucha. Klasa pesymistycznej złożoności obliczeniowej algorytmu N jest równa O(n × m), gdzie n oznacza liczbę znaków tekstu, a m liczbę znaków wzorca. Jednakże w typowych warunkach algorytm pracuje w czasie O(n), ponieważ zwykle wystarczy porównanie kilku początkowych znaków okna z wzorcem, aby stwierdzić, iż są one niezgodne.