Wyszukiwanie wzorca w tekście

powrót

Definicja. Wzorzec to spójny podciąg (podtekst), który występuje w danym ciągu znaków. Załóżmy, że szukamy słowa $$motyw$$ w słowie $$lokomotywa$$. W tym przykładzie $$motyw$$ jest wzorcem i występuje on w słowie $$lokomotywa$$ począwszy od piątej pozycji.

W tym artykule przedstawione zostanie naiwne rozwiązanie tego problemu. Algorytm będzie szukał pierwszego wystąpienia wzorca w tekście.

Niech

$$dlt$$

będzie przechowywać liczbę znaków w tekście, natomiast

$$dlw$$

liczbę znaków we wzorcu.

Zauważmy teraz, że wystarczy przeszukać tylko $$dlt-dlw+1$$ pierwszych liter w tekście, ponieważ każda następna pozycja to zbyt mało znaków, żeby dopasować do wzorca:

dla słowa

$$lokomotywa$$ 

sprawdzamy tylko

  • $$lokom$$ - przerywamy pętlę po pierwszym znaku - $$l\neq m$$
  • $$okomo$$ - przerywamy pętlę po pierwszym znaku - $$o\neq m$$ 
  • $$komot$$ - przerywamy pętlę po pierwszym znaku - $$k\neq m$$ 
  • $$omoty$$ - przerywamy pętlę po pierwszym znaku - $$o\neq m$$ 
  • $$motyw$$ - tu mamy wzorzec na 5 pozycji
  • $$otywa$$ - znaleźliśmy już wzorzec, a więc dalej nie trzeba szukać
  • kolejne podciągi są zbyt krótkie, aby dopasować wzorzec.

 

Oczywiście, gdy znajdziemy wzorzec to przerywamy dalsze poszukiwania i jeśli jakiś znak się nie zgadza, to nie szukamy dalej w danym podciągu.

Algorytm dopasowuje pierwszą literę wzorca, gdy taką napotka, dopasowuje następne.

Do wypisania wyniku wykorzystano manipulatory, które opisane są w tym miejscu.

Rozwiązanie w C++:

#include
#include
using namespace std;

int main()
{
  char tekst[100], wzorzec[100];
 
  cout<<"Podaj tekst: ";
  cin.getline(tekst,100);
 
  cout<<"Podaj wzorzec: ";
  cin.getline(wzorzec,100);
 
  //naiwne wyszukiwanie wzorca w tekscie
 
  int t = 0, w; //do poruszania się po tablicach znaków
  int dl_t = strlen(tekst), dl_w = strlen(wzorzec);
  bool ok = 0;
 
  for(int i=0; i <= dl_t - dl_w; i++)
  {
      ok = 1;
      
      //sprawdzamy, czy zgadzają się pozostałe znaki
      for(int j=0; j<dl_w; j++)
      if(tekst[j+i]!=wzorzec[j]) //jesli nie zgadzają się
      {
        ok = 0;  //gdy tu wejdziemy, to ok = 0
        break;
      }
 
      if(ok) //jesli wszystkie litery się zgadzają (ok = 1)
      {
        cout<<"Wzorzec znaleziono. Początek na "
          <<i+1<<" pozycji\n";
 
        cout<<tekst<<endl;
 
        cout.fill(' '); 
        cout.width(i+dl_w);
 
        cout<<wzorzec<<endl;
 
        break;
      }
  }
  if(!ok)
    cout<<"Wzorca nie znaleziono!";
 
  cin.get();
  return 0;
}