Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Naiwne wyszukiwanie wzorca w tekście

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

W łańcuchu znakowym s  należy znaleźć wszystkie wystąpienia wzorca p.

Rozwiązanie nr 1

Problem Wyszukiwania Wzorca WW ( ang. pattern matching ) to jeden z podstawowych problemów tekstowych, który intensywnie badali wybitni informatycy. Rozwiązaniem jest wskazanie w ciągu s  wszystkich pozycji i  takich, że zachodzi równość:

s [ i  : i  + | p | ] = p

Oznacza to, iż wzorzec p  jest fragmentem łańcucha s  występującym na pozycji i-tej.

Algorytm N – naiwny – ustawia okno o długości wzorca p  na pierwszej pozycji w łańcuchu s. Następnie sprawdza, czy zawartość tego okna jest równa wzorcowi p. Jeśli tak, pozycja okna jest zwracana jako wynik, po czym okno przesuwa się o jedną pozycję w prawo i cała procedura powtarza się. Algorytm kończymy, gdy okno wyjdzie poza koniec łańcucha. Klasa pesymistycznej złożoności obliczeniowej algorytmu N jest równa O ( n  × m  ), gdzie n  oznacza liczbę znaków tekstu, a m  liczbę znaków wzorca. Jednakże w typowych warunkach algorytm pracuje w czasie O ( n  ), ponieważ zwykle wystarczy porównanie kilku początkowych znaków okna z wzorcem, aby stwierdzić, iż są one niezgodne.

Algorytm naiwny wyszukiwania wzorca w łańcuchu tekstowym

Wejście:

s  –  łańcuch znakowy
p  –  łańcuch wzorca

Wyjście:

Wszystkie pozycje wzorca p  w łańcuchu s.

Zmienne pomocnicze:

i  –  pozycja okna, i  ∈ N.
n  – długość łańcucha s, n  ∈ N.
m  – długość wzorca p, m  ∈ N.

Lista kroków:

K01: n  ← | s | obliczamy długość łańcucha s
K02: m  ← | p | obliczamy długość wzorca p
K03: Dla i  = 0, 1, ... n  - m:
wykonuj krok K04
 
K04:     Jeśli p = s [ i  : i + m  ],
    to pisz i
okno zawiera wzorzec?
K05: Zakończ  

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program generuje 60 znakowy łańcuch zbudowany z pseudolosowych kombinacji liter A, B i C. Następnie losuje 3 literowy wzorzec z tych samych liter i algorytmem naiwnym wyszukuje wszystkie wystąpienia wzorca w łańcuchu. Pozycję wzorca zaznacza znakiem ^.
Pascal
// Algorytm WWN
// Data:   29.05.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  s, p : ansistring;
  i : integer;

begin
  randomize;

  // generujemy łańcuch

  s := '';
  for i := 1 to 60 do s := s + chr ( 65 + random ( 3 ) );

  // generujemy wzorzec

  p := '';
  for i := 1 to 3 do p := p + chr ( 65 + random ( 3 ) );

  // wypisujemy wzorzec

  writeln ( p ); 

  // wypisujemy łańcuch

  writeln ( s );

  // szukamy wzorca w łańcuchu

  for i := 1 to 58 do
    if p = copy ( s, i, 3 ) then write ( '^' ) else write ( ' ' );

  writeln;
  writeln;
end.
C++
// Algorytm WWN
// Data:   29.05.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

using namespace std;

int main( )
{
  string s, p;
  int i;
  
  srand ( ( unsigned )time ( NULL ) );

  // generujemy łańcuch

  s = "";
  for( i = 0; i < 60; i++ ) s += char ( 65 + ( rand( ) % 3 ) );

  // generujemy wzorzec

  p = "";
  for( i = 0; i < 3; i++ ) p += char ( 65 + ( rand( ) % 3 ) );

  // wypisujemy wzorzec

  cout << p << endl; 

  // wypisujemy łańcuch

  cout << s << endl;

  // szukamy wzorca w łańcuchu

  for( i = 0; i < 58; i++ )
    cout << ( p == s.substr ( i, 3 ) ? "^": " " );

  cout << endl << endl;
  return 0;
}
Basic
' Algorytm WWN
' Data:   29.05.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Dim As String s, p
Dim As Integer i

Randomize

' generujemy łańcuch

s = ""
For i = 1 To 60: s += Chr ( 65 + Cint ( Rnd * 2 ) ): Next

' generujemy wzorzec

p = ""
For i = 1 To 3: p += Chr ( 65 + Cint ( Rnd * 2 ) ): Next

' wypisujemy wzorzec

Print p

' wypisujemy łańcuch

Print s

' szukamy wzorca w łańcuchu

For i = 1 To 58
  If p = Mid ( s, i, 3 ) Then Print "^";: Else Print " ";
Next
Print: Print
End
Wynik:
ABB
ABCBBAAABBCAABCBBABBBCCBAABCBBCCABCBACBBAACAABCCCABACCCACAAA
       ^         ^
Wyszukiwanie wzorca algorytmem N
(C)2020 mgr Jerzy Wałaszek


...

Na początek:  podrozdziału   strony 

Rozwiązanie nr 2

Algorytm N możemy nieco usprawnić wykorzystując ideę wartowników. Na końcu łańcucha oraz wzorca umieszczamy dwa różne znaki. Zapobiegną one wyjściu poza obszar łańcucha przy testowaniu znaków w oknie i we wzorcu. Dzięki nim odpadnie sprawdzanie zakresu indeksów w oknie – algorytm wykona mniej operacji.

Algorytm naiwny wyszukiwania wzorca z wartownikami

Wejście:

s  –  łańcuch znakowy.
p  –  łańcuch wzorca.

Wyjście:

Wszystkie pozycje wzorca p  w łańcuchu s.

Zmienne pomocnicze:

i  –  pozycja okna w łańcuchu s, i  ∈ N.
j  – pozycja wewnątrz okna, j  ∈ N.
n  – długość łańcucha s, n  ∈ N.
m  – długość wzorca p, m  ∈ N.

Lista kroków:

K01: n  ← | s | obliczamy długość łańcucha s
K02: m  ← | p | obliczamy długość wzorca p
K03: s  ← s  + 'X' na końcu łańcucha umieszczamy wartownika
K04: p  ← p  + 'Y' na końcu wzorca umieszczamy innego wartownika
K05: Dla i  = 0, 1, ..., n  - m:
wykonuj kroki K06...K08
pozycje okna
K06:     j  ← 0 pozycja w oknie i we wzorcu
K07:     Dopóki s [ i  + j  ] = p [ j  ],
    wykonuj j  ← j + 1
szukamy pierwszego różnego znaku okna i wzorca
K08:     Jeśli j  = m,
    to pisz i
sprawdzamy, czy cały wzorzec wystąpił w oknie
K09: Usuń ostatni znak z s pozbywamy się wartownika z łańcucha
K10: Usuń ostatni znak z p pozbywamy się wartownika ze wzorca
K11: Zakończ  

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program generuje 60 znakowy łańcuch zbudowany z pseudolosowych kombinacji liter A, B i C. Następnie losuje 3 literowy wzorzec z tych samych liter i algorytmem naiwnym wyszukuje wszystkie wystąpienia wzorca w łańcuchu. Pozycję wzorca zaznacza znakiem ^.
Pascal
// Algorytm WWN z wartownikami
// Data:   30.05.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

var
  s, p : ansistring;
  i, j : integer;

begin
  randomize;

  // generujemy łańcuch

  s := '';
  for i := 1 to 60 do s := s + chr ( 65 + random ( 3 ) );

  // generujemy wzorzec

  p := '';
  for i := 1 to 3 do p := p + chr ( 65 + random ( 3 ) );

  // wypisujemy wzorzec

  writeln ( p );

  // wypisujemy łańcuch

  writeln ( s );

  // dodajemy wartowników

  s := s + 'X'; p := p + 'Y';

  // szukamy wzorca w łańcuchu

  for i := 1 to 58 do
  begin
    j := 0;
    while s [ i + j ] = p [ j + 1 ] do inc ( j );
    if j = 3 then write ( '^' ) else write ( ' ' );
  end;

  writeln;
  writeln;
end.
C++
// Algorytm WWN z wartownikami
// Data:   30.05.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

int main( )
{
  string s, p;
  int i, j;

  srand ( ( unsigned )time ( NULL ) );

  // generujemy łańcuch

  s = "";
  for( i = 0; i < 60; i++ ) s += char ( 65 + ( rand( ) % 3 ) );

  // generujemy wzorzec

  p = "";
  for( i = 0; i < 3; i++ ) p += char ( 65 + ( rand( ) % 3 ) );

  // wypisujemy wzorzec

  cout << p << endl; 

  // wypisujemy łańcuch

  cout << s << endl;

  // dodajemy wartowników

  s += "X"; p += "Y";

  // szukamy wzorca w łańcuchu

  for( i = 0; i < 58; i++ )
  {
    for( j = 0; s [ i + j ] == p [ j ]; j++ ) ;
    cout << ( j == 3 ? "^": " " );
  }

  cout << endl << endl;
  return 0;
}
Basic
' Algorytm WWN z wartownikami
' Data:   30.05.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Dim As String s, p
Dim As Integer i, j

Randomize

' generujemy łańcuch

s = ""
For i = 1 To 60: s += Chr ( 65 + Cint ( Rnd * 2 ) ): Next

' generujemy wzorzec

p = ""
For i = 1 To 3: p += Chr ( 65 + Cint ( Rnd * 2 ) ): Next

' wypisujemy wzorzec

Print p

' wypisujemy łańcuch

Print s

' dodajemy wartowników

s += "X": p += "Y"

' szukamy wzorca w łańcuchu

For i = 1 To 58
  j = 0
  While Mid ( s, i + j, 1 ) = Mid ( p, j + 1, 1 ): j += 1: Wend
  If j = 3 Then Print "^";: Else Print " ";
Next

Print: Print
End
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.