Algorytm wyszukiwania wzorca w tekście metodą naiwną

Krok po kroku jak działa algorytm

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 wyszukiwania wzorca w tekście metodą naiwną

2

3

4

5

1

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.

implementacja algorytmu w c++

implementacja algorytmu w Pythonie

• Wybierz wzorzec, który chcesz wyszukać w tekście.

• Przesuń wzorzec od lewej do prawej po tekście, porównując każdy znak tekstu z kolejnymi znakami wzorca.

• Jeśli wszystkie znaki się zgadzają, to znaczy, że znaleźliśmy wystąpienie wzorca w tekście. Zapisz pozycję, na której wystąpił wzorzec.

• Kontynuuj przeszukiwanie tekstu, porównując kolejne znaki z wzorcem, aż do końca tekstu.

• Jeśli żadne wystąpienie wzorca nie zostało znalezione, to zakończ przeszukiwanie tekstu.

BIBLIOGRAFIA https://cloud-5.edupage.org/cloud/Naiwne_i_BM_wyszukiwanie_wzorca_w_tekscie__Palindromy.pdf?z%3AcAHYSx9mZMk8uB%2ByXXvgKpiw3h1FRqyLtqWrBH2%2FiIffFyzAh35DQWV%2FUnqTzEHW https://www.google.com/search?q=Algorytm+wyszukiwania+wzorca+w+tek%C5%9Bcie+metod%C4%85+naiwn%C4%85&source=lmns&tbm=vid&client=firefox-b-d&hl=pl&sa=X&ved=2ahUKEwjzu9P30-3-AhUXzyoKHQUCCbQQ_AUoBHoECAEQBA#fpstate=ive&vld=cid:14bcb6ce,vid:f_oU80GD9UI https://www.google.com/search?q=wyszukiwanie+wzorca+w+tek%C5%9Bcie+metod%C4%85+naiwn%C4%85+c%2B%2B&client=firefox-b-d&hl=pl&tbm=vid&ei=yRNdZLewO9TQqwGKpKyICg&oq=Algorytm+wyszukiwania+wzorca+w+tek%C5%9Bcie+metod%C4%85+naiwn%C4%85+&gs_lcp=Cg1nd3Mtd2l6LXZpZGVvEAEYADIGCAAQFhAeOgUIABCABFDpA1jpA2DJEmgAcAB4AIABfIgB6AGSAQMwLjKYAQCgAQHAAQE&sclient=gws-wiz-video#fpstate=ive&vld=cid:3baa8ac8,vid:9tBaZc9wO1I https://www.youtube.com/watch?v=uEphLOvKRn0