Want to create interactive content? It’s easy in Genially!
Get started free
Algorytm wyszukiwania wzorca w tekście metodą naiwną
j.maciejak2703
Created on May 11, 2023
Start designing with a free template
Discover more than 1500 professional designs like these:
View
Interactive Image with Information
View
Interactive Human Body Image
View
Interactive Artwork Image
View
Interactive Product Image
View
Essential Square Interactive Image
View
Akihabara Vertical Interactive Image
View
Interactive Nature Image
Transcript
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