Naiwne wyszukiwanie wzorca

Algorytm

Naiwne wyszukiwanie wzorca jest najprostszą metodą sprawdzania czy w przeszukiwanym tekście można znaleźć określone wyrażenie. Jego prosta idea jest wystarczająca, aby wykonać zadanie, ale w przypadku większych danych algorytm ten może okazać się mało efektywny.

Zasada działania

Przypuśćmy, że mamy tekst o długości n oraz wzorzec o długości m. Dla każdej i-tej litery należy sprawdzić m kolejnych znaków czy są zgodne z znakami we wzorcu. Oczywiście porównania są wykonywane dopóki jest sens czyli istnieje kolejne m liter począwszy od i-tego indeksu. Złożoność tego algorytmu w najgorszym przypadku wynosi Θ(n·m) kiedy w każdym sprawdzanym zakresie nie zgadza się tylko ostatni znak. Zazwyczaj jednak algorytm można porównywać z liniowym Θ(n), ponieważ zazwyczaj w każdy fragmencie nie zgadza się już pierwszy znak.

Poniżej znajduje się lista kroków algorytmu:

1. Wczytaj tekst i wzorzec
2. Przypisz m długość tekst i n długość wzorzec
3. Dla każdego indeksu i z [0, n - m + 1]:
   • Wybierz ciąg [i, i + m] z tekstu i porównaj z wzorzec
   • Jeśli są identyczne zwróć, że wzorzec istnieje, w przeciwnym razie kontynuuj pętle
4. Jeśli program wcześniej nie zwrócił wyniku to zwróć, że wzorzec nie występuje

Przykład działania

Weźmy tekst "INFORMACJA" i wyszukajmy tekst "MA" kolejno należy porównywać następujące fragmenty:

Szukany wzorzec został odnaleziony. W zależności od przeznaczenia algorytmu można go kontynuować w celu zliczenia wszystkich wystąpień wzorca, albo przerwać po znalezieniu pierwszego wystąpienia wzorca.

Implementacja

Przypuśćmy, że funkcja czyWystepuje() będzie przyjmować dwa argumenty tablicy znaków: tekst i wzorzec. Wynikiem działania funkcji jest wartość logiczna czy w zmiennej tekst występuje wzorzec. Poniżej znajduje się gotowy kod realizujący to zadanie:

1. bool czyWystepuje(char* tekst, char* wzorzec) {
2.   for (int i = 0; tekst[i]; i++) {
3.     int j = 0;
4.     while (wzorzec[j] != '\0' && tekst[i + j] == wzorzec[j])
5.       j++;
6.     if (j > 0 && wzorzec[j] == '\0')
7.       return true;
8.   }
9.   return false;
10. }

(2.) Dla każdego znaku w tekście: (3.) sprawdzamy czy kolejnego znaki tekstu od i-tej pozycji są identyczne jak we wzorcu. (5.) Po zakończeniu pętli możliwe są dwa przypadki: wzorzec pasuje i wtedy indeks j będzie większy od zera i będzie wskazywał we wzorcu znak końca danych. W takim przypadku (6.) należy zwrócić prawdę, ponieważ tekst występuje (nieważne ile razy i nieważne gdzie). W przeciwnym razie należy kontynuować pętle for. Jeśli po sprawdzeniu wszystkich znaków wzorzec nie został odnaleziony to (9.) należy zwrócić fałsz.

Powyższy algorytm można zoptymalizować nie sprawdzając ostatnich m - 1 indeksów w tekst, ponieważ dalszy fragment jest krótszy od długości wzorca m. Niemniej należy pamiętać, że w ten algorytm oszczędza czas nie szukając długości tekst i wzorzec.

Testowanie funkcji

W celu przetestowania funkcji najlepiej jest zapisać dodatkową funkcję testującą, która dla podanych parametrów wyświetli zrozumiałe dla człowieka dane:

1. void czyWystepujeTEST(char* tekst, char* wzorzec) {
2.   cout << "W tekscie \"" << tekst << "\" ";
3.   cout << (czyWystepuje(tekst, wzorzec) ? "" : "nie ");
4.   cout << "wystepuje \"" << wzorzec << "\"\n";;
5. }

Z kolei w funkcji main() można przetestować działanie funkcji tak jak w kodzie poniżej.

1. int main () {
2.   char* tekst = "ab abb aab aaabb";
3.   czyWystepujeTEST(tekst, "a");
4.   czyWystepujeTEST(tekst, "ab");
5.   czyWystepujeTEST(tekst, " b");
6.   system("pause");
7.   return 0;
8. }

Testowanie można wykonać bez pisania dodatkowej funkcji testującej, ale w ten sposób łatwiej jest zapanować nad sprawdzanymi przypadkami i ujednolicić tekst na konsoli.

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz funkcję o nagłówku ileWystapien(), która będzie przyjmować tablice znaków tekst i wzorzec, następnie zwróci liczbę całkowitą oznaczającą ilość wystąpień wzorzec w tekst. Przetestuj działanie funkcji.

Przykładowo dla tekst "tartak" i wzorca "ta" program ma zwrócić 2. Z kolei dla "informacja" i "pl" zwróci 0.

• Kod źródłowy Zadanie 1