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++:

//algorytm.edu.pl
#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!";

  return 0;
}

Rozwiązanie z wykorzystaniem typu string oraz funkcji:

//wyszukiwanie wzorca w tekście
//Zwrócenie pozycji wystąpienia pierwszego znaku wzorca w tekście
//lub -1, jeśli wzorca nie znaleziono
//algorytm.edu.pl 
#include<bits/stdc++.h>

using namespace std;

int szukaj(string wzorzec, string tekst)
{
	for(int i=0;i <= tekst.size() - wzorzec.size();i++) //po tekście
	{
		int c = 0;
		for(int j=0;j<wzorzec.size();j++)
		{
			if(wzorzec[j] != tekst[i + c])
				break;
			if(j == wzorzec.size() - 1)
				return i+1;
			++c;
		}
	}
	return -1;
}
int main()
{
	string wzorzec, tekst;
	cout<<"Podaj tekst: ";
	cin>>tekst;
	cout<<"Podaj wzorzec: ";
	cin>>wzorzec;
	
	int pos = szukaj(wzorzec, tekst);
	
	if(pos == -1)
		cout<<"Wzorca nie znaleziono";
	else
		cout<<"Wzorzec znaleziono na "<<pos<<" pozycji";
	
	return 0;
}

Dla obiektu string zdefiniowana jest metoda, która wyszukuje wzorzec w tekście w czasie liniowym. Metodę find opisano w tym miejscu.