Zamów podręcznik wydawnicta MiGra (sklep wydawnictwa)
Wyszukiwanie wzorca w tekście. Metoda naiwna
Wyszukiwanie wzorca w tekście polega na porównaniu kolejnych znaków wzorca z kolejnymi znakami w tekście przeszukiwanym. Wynik szukania może być wykorzystany do zliczania wystąpienia wzorca, zamiany znalezionych ciągów znaków nowym ciągiem, usunięciem wystąpień wzorca z tekstu itp.
Wyszukiwanie wzorca w tekście obrazuje poniższy rysunek
(Źródło: Informatyka dla szkół ponadpodstawowych. Zakres podstawowy Klasa III wyd. MiGra)
Algorytm wyszukiwania wzorca w tekście metodą naiwną przedstawia poniższy schemat
Realizację tego algorytmu możemy wykonać tym kodem.
#include <iostream>
#include <conio.h>
#include <string.h>
using namespace std;
int main()
{
string txt="";
cout << "Wprowadz dowolny ciag znakow: " << endl;
cin>>txt;
int dt=0;//dlugosc tekstu
dt=txt.length();
cout<<"Badany tekst zawiera znakow: "<<dt<<endl;
cout <<"Wprowadz znaki wzorca: "<< endl;
string wzr="";
cin>>wzr;
int dw=0;//dlugosc wzorca
dw=wzr.length();
cout<<"Wzorzec zawiera znakow: "<<dw<<endl;
//petla po znakach tektu zrodlowego
int licznik=0;
for(int i=0;i<dt;i++){
int j=0;
//sparwdzaj i zliczaj wystapienia tych samych sasiednich znakow
while(j<dw && txt[i+j]==wzr[j])j++;
//jak suma j-otow jest rowna dlugosci wzorca,
//to oznacza ze wzorzec wystapil
if(j==dw){
licznik++;
cout<<"Wzorzec wystapil po raz: "<<licznik<<", pozycja tego wystapienia: "<<i+1<<endl;
}
}
getch();
return 0;
}
Metoda wykorzystuje dwie pętle. Pętla główna wykonywana jest poprzez odczyt znak po znaku tekstu źródła. Druga wewnętrzna pętla porównuje znak po znaku wzorca i odczytanego znaku źródła. W przypadku zgodności zlicza sumę występowania zgodności.
