Algorytm wyszukiwania wzorca w tekście metodą naiwną

Algorytm wyszukiwania wzorca w tekście metodą naiwną

Metoda naiwna to najprostszy algorytm wyszukiwania wzorca w tekście. Polega na iteracyjnym porównywaniu kolejnych podciągów tekstu z wzorcem. Dla każdego możliwego przesunięcia wzorca w tekście, porównywane są kolejne znaki tekstu z kolejnymi znakami wzorca.

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 naiwny ma złożoność czasową O(mn), gdzie m to długość wzorca, a n to długość tekstu. Algorytm ten jest prosty, ale ma niską wydajność dla dużych zbiorów danych, gdyż wymaga wielokrotnego porównywania każdego znaku z wzorcem.

Krok po kroku jak działa algorytm

implementacja algorytmu w c++

implementacja algorytmu w Pythonie