W łańcuchu znakowym s znaleźć wszystkie wystąpienia wzorca p.
Problem Wyszukiwania Wzorca – WW (ang. pattern matching) to jeden z podstawowych problemów tekstowych, który intensywnie badali wybitni informatycy.
2. Rozwiązanie.
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.
3. Rozwiązanie w C++
Brak komentarzy:
Prześlij komentarz