Algorytm wyszukiwania wzorca w tekście
Wyszukiwanie wzorca w tekście źródłowym 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.
Algorytm naiwny wyszukiwania wzorca w tekście polega na przeglądaniu kolejnych znaków w głównej pętli bazującej na znakach wzorca pętlą wewnętrzną znaków wzorca.
Pętla wewnętrzna działa na znakach wzorca i gdy wystąpi zgodność znaków dochodzi do sumowania zgodności. Jeżeli suma zliczeń jest równa długości wzorca, to oznacza że wzorzec występuje w tekście źródłowym.
Schemat blokowy algorytmu naiwnego wyszukiwania wzorca w tekście
Kod funkcji algorytmu wyszukiwania wzorca w tekście metodą naiwną zapisany w języku C# działający według podanego powyżej schematu blokowego.
Wskazówka:
void szukajWzorca(String tZrodlo,String tWzorzec,TextBox txtWynik)
{
//wyczyść poprzednie wyniki wystąpień
txtWynik.Text = "";
//szuka i zlicza ilość wystąpień wzorca w tekście źródłowym
//odczytaj długość tekstu źródłowego
int dt=tZrodlo.Length;
//odczytaj długość tekstu wzorca
int dw =tWzorzec.Length;
//licznik wystapień wzorca
//wartośc zero oznacza, że wzorzec nie występuje w źródle
int licznik = 0;
for (int i = 0; i < dt; i++)
{
int j = 0;
//sparwdzaj i zliczaj wystapienia tych samych sasiednich znakow
while (j < dw && tZrodlo[i + j] == tWzorzec[j]) j++;
//jak suma j-otow jest rowna dlugosci wzorca,
//to oznacza ze wzorzec wystapil
if (j == dw)
{
licznik++;
txtWynik.AppendText("wzorzec wystąpił po raz: "
+ licznik.ToString()
+ " pozycja znaku: "
+ i.ToString()
+ Environment.NewLine);
}
}
}
Przykładowa aplikacja wykorzystująca algorytm naiwnego wyszukiwania wzorca w tekście
Pełny kod klasy Form dla formatki utworzonej aplikacji desktopowej
Form1.cs:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace _23AlgWyszukiwanieWzorca
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
void szukajWzorca(String tZrodlo,String tWzorzec,TextBox txtWynik)
{
//wyczyść poprzednie wyniki wystąpień
txtWynik.Text = "";
//szuka i zlicza ilość wystąpień wzorca w tekście źródłowym
//odczytaj długość tekstu źródłowego
int dt=tZrodlo.Length;
//odczytaj długość tekstu wzorca
int dw =tWzorzec.Length;
//licznik wystapień wzorca
//wartośc zero oznacza, że wzorzec nie występuje w źródle
int licznik = 0;
for (int i = 0; i < dt; i++)
{
int j = 0;
//sparwdzaj i zliczaj wystapienia tych samych sasiednich znakow
while (j < dw && tZrodlo[i + j] == tWzorzec[j]) j++;
//jak suma j-otow jest rowna dlugosci wzorca,
//to oznacza ze wzorzec wystapil
if (j == dw)
{
licznik++;
txtWynik.AppendText("wzorzec wystąpił po raz: "
+ licznik.ToString()
+ " pozycja znaku: "
+ i.ToString()
+ Environment.NewLine);
}
}
}
private void button1_Click(object sender, EventArgs e)
{
szukajWzorca(textBox1.Text, textBox2.Text, textBox3);
}
}
}
