Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

czytaj więcej

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 {tex}motyw{/tex} w słowie {tex}lokomotywa{/tex}. W tym przykładzie {tex}motyw{/tex} jest wzorcem i występuje on w słowie {tex}lokomotywa{/tex} 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

{tex}dlt{/tex}

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

{tex}dlw{/tex}

liczbę znaków we wzorcu.

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

dla słowa

{tex}lokomotywa{/tex} 

sprawdzamy tylko

  • {tex}lokom{/tex} - przerywamy pętlę po pierwszym znaku - {tex}l\neq m{/tex}
  • {tex}okomo{/tex} - przerywamy pętlę po pierwszym znaku - {tex}o\neq m{/tex} 
  • {tex}komot{/tex} - przerywamy pętlę po pierwszym znaku - {tex}k\neq m{/tex} 
  • {tex}omoty{/tex} - przerywamy pętlę po pierwszym znaku - {tex}o\neq m{/tex} 
  • {tex}motyw{/tex} - tu mamy wzorzec na 5 pozycji
  • {tex}otywa{/tex} - 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<iostream>
#include<cstring>
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;
}