Wyszukiwanie Wzorca w Tekście

Wyobraź sobie, że piszesz wyszukiwarkę na stronie (Ctrl+F) i musisz znaleźć wyraz "Ala" w zdaniu "Kot zjadł Alana". To klasyczny problem informatyczny nazywany wyszukiwaniem wzorca w tekście.

Mamy tekst główny (T) oraz krótszy wzorzec (W). Szukamy wszystkich momentów, w których W występuje w T jako spójny kawałek.

Metoda Naiwna (Podstawowa)

Jak nazwa wskazuje, ten algorytm robi dokładnie to, co zrobiłby człowiek – po kolei. Przykładamy wzorzec na samym początku tekstu i sprawdzamy po kolei każdą literkę. Jeśli się nie zgadza, przesuwamy wzorzec w prawo o 1 okienko i zaczynamy od nowa. Złożoność to $O(N \cdot M)$.

Python

def szukaj_wzorca(tekst, wzorzec):
    N = len(tekst)
    M = len(wzorzec)
    
    # Przesuwamy "okienko" od 0 aż do momentu, 
    # w którym wzorzec przestałby się mieścić w tekście
    for i in range(N - M + 1):
        pasuje = True
        
        for j in range(M):
            if tekst[i + j] != wzorzec[j]:
                pasuje = False
                break # Jeśli choć jedna się nie zgadza, odpuszczamy
                
        if pasuje:
            print(f"Wzorzec znaleziony na indeksie {i}")

szukaj_wzorca("ABRACADABRA", "ABRA")

C++

#include <iostream>
#include <string>
using namespace std;

void szukajWzorca(string tekst, string wzorzec) {
    int N = tekst.length();
    int M = wzorzec.length();
    
    for (int i = 0; i <= N - M; i++) {
        bool pasuje = true;
        
        for (int j = 0; j < M; j++) {
            if (tekst[i + j] != wzorzec[j]) {
                pasuje = false;
                break;
            }
        }
        
        if (pasuje) {
            cout << "Wzorzec na indeksie " << i << endl;
        }
    }
}

[!TIP] Dla dociekliwych: Algorytm Knutha-Morrisa-Pratta (KMP) Metoda naiwna jest powolna. Algorytm KMP działa dużo sprytniej! Wykorzystuje wcześniej wyliczoną tablicę tzw. "prefikso-sufiksów" (LPS), dzięki czemu po napotkaniu błędu wie dokładnie, ile liter może z całą pewnością przeskoczyć bez ich ponownego sprawdzania. Redukuje to czas działania do $O(N + M)$.