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

©2023 mgr Jerzy Wałaszek
I LO w Tarnowie

Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

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

Tutaj znajdziesz oryginalny tekst R.S.Boyera oraz J.S.Moore'a z roku 1977. Dokument jest napisany w języku angielskim.

Heurystyki algorytmu Boyera-Moore'a

Uproszczony algorytm Boyera-Moore'a reaguje tylko na niezgodność znaku wykorzystując wyliczoną wcześniej tablicę Last do znalezienia przesunięcia okna wzorca p  w obrębie przeszukiwanego tekstu s. Postępowanie to nazywamy heurystyką niepasującego znaku (ang. bad character heuristics ). Zupełnie nie korzystamy tutaj z informacji, iż pewien sufiks b  wzorca p  pasował do przeszukiwanego tekstu:

obrazek

Pełna wersja algorytmu nie wyrzuca do kosza tej informacji. Rozważmy możliwe dwa przypadki:

  1. Pasujący sufiks b  powtarza się wewnątrz wzorca. Dodatkowo żądamy, aby znak C bezpośrednio poprzedzający ten fragment tekstu był różny od znaku B (B jest oznaczeniem symbolicznym, a nie konkretną literą! ), gdyż w przeciwnym razie otrzymamy natychmiastową niezgodność z przeszukiwanym tekstem. Okno wzorca przesuwamy, tak aby uzyskać pokrycie pasującego fragmentu b  z pasującym do niego fragmentem b  przeszukiwanego tekstu.

obrazek

  1. Pasujący sufiks b  nie powtarza się wewnątrz wzorca. Jednakże istnieje prefikso-sufiks bb wzorca zawarty w pasującym sufiksie b (porusz algorytm KMP ). W takim przypadku okno wzorca przesuwamy, tak aby uzyskać pokrycie prefikso-sufiksów we wzorcu i w przeszukiwanym tekście:

obrazek

Jeśli prefikso-sufiks jest pusty, to okno wzorca można przesunąć o całą długość wzorca beż żadnej straty dla wyników poszukiwań. W efekcie uzyskujemy bardzo ciekawą własność algorytmu Boyera-Moore'a – im wzorzec p  jest dłuższy, tym szybciej przebiega wyszukiwanie, ponieważ algorytm przeskakuje większe partie tekstu.

Opisana w tych dwóch punktach strategia postępowania nosi nazwę heurystyki pasującego sufiksu (ang. good suffix heuristics ). W wyniku jej zastosowania otrzymujemy przesunięcie okna wzorca bez pomijania możliwych wystąpień w przeszukiwanym tekście.

Pełny algorytm Boyera-Moore'a wykorzystuje obie heurystyki – nie pasującego znaku (opisana w poprzednim rozdziale) oraz pasującego sufiksu, a wynikowe przesunięcie okna wzorca jest większym z tych dwóch wyliczonych przesunięć.

Na początek:  podrozdziału   strony 

Wyznaczanie tablicy przesunięć BMNext

Do wyznaczenia przesunięcia w przypadku heurystyki pasującego sufiksu będzie nam potrzebna tablica BMNext zawierająca wartości przesunięć dla poszczególnych sufiksów wzorca ( tablica ta jest niejako odwróceniem tablicy KMPNext obecnej w algorytmie KMP ). Wyznaczamy ją w dwóch etapach.

Etap 1

Ten etap jest bardzo podobny do przetwarzania wzorca w algorytmie KMP. Pasujący sufiks bb  jest prefikso-sufiksem pewnego sufiksu b  wzorca p:

obrazek

Musimy ustalić prefikso-sufiksy sufiksów wzorca, jednakże w porównaniu z algorytmem KMP będzie obowiązywało odwrotne odwzorowanie pomiędzy prefikso-sufiksem, a najkrótszym sufiksem zawierającym ten prefikso-sufiks. Jednocześnie musimy zagwarantować, iż dany prefikso-sufiks nie może być rozszerzalny w lewo (patrz znaki B i C we wzorcu) przez znak B, który spowodował niezgodność z przeszukiwanym tekstem. W przeciwnym razie po przesunięciu okna wzorca otrzymalibyśmy natychmiastową niezgodność, ponieważ w tym samym miejscu znów znalazłby się niezgodny znak B.

W etapie 1 obliczana jest pomocnicza tablica П o elementach indeksowanych od 0 do m (m  = | p | ). Element П [ i  ] zawiera początkową pozycję maksymalnego prefikso-sufiksu sufiksu wzorca rozpoczynającego się na pozycji i-tej.

Przykład:

Dla wzorca ABBABBBA tablicę П wyznaczymy następująco:

Tworzenie tablicy П Opis 
i: 0 1 2 3 4 5 6 7 8 
p: A B B A B B B A
П: . . . . . . . . 9 
Na pozycji m = 8 jest sufiks pusty, Ponieważ nie posiada on prefikso-sufiksu, do П [ 8 ] wpisujemy 9 
i: 0 1 2 3 4 5 6 7 8 
p: A B B A B B B A 
П: . . . . . . . 8 9
Na pozycji 7 jest sufiks A. Posiada on prefikso-sufiks pusty rozpoczynający się na pozycji 8. 
i: 0 1 2 3 4 5 6 7 8 
p: A B B A B B B A 
П: . . . . . . 8 8 9
Sufiks BA również posiada prefikso-sufiks pusty. 
i: 0 1 2 3 4 5 6 7 8 
p: A B B A B B B A 
П: . . . . . 8 8 8 9
Sufiks BBA posiada prefikso-sufiks pusty 
i: 0 1 2 3 4 5 6 7 8 
p: A B B A B B B A 
П: . . . . 8 8 8 8 9
Sufiks BBBA posiada prefikso-sufiks pusty 
i: 0 1 2 3 4 5 6 7 8 
p: A B B A B B B A 
П: . . . 7 8 8 8 8 9
Sufiks ABBBA posiada prefikso-sufiks A rozpoczynający się na pozycji 7. 
i: 0 1 2 3 4 5 6 7 8 
p: A B B A B B B A 
П: . . 6 7 8 8 8 8 9
Sufiks BABBBA rozszerza prefikso-sufiks poprzedniego sufiksu do prefikso-sufiksu BA rozpoczynającego się na pozycji 6. 
i: 0 1 2 3 4 5 6 7 8 
p: A B B A B B B A 
П: . 5 6 7 8 8 8 8 9
Sufiks BBABBBA znów rozszerza prefikso-sufiks poprzedniego sufiksu do prefikso-sufiksu BBA rozpoczynającego się na pozycji 5. 
i: 0 1 2 3 4 5 6 7 8 
p: A B B A B B B A 
П: 7 5 6 7 8 8 8 8 9
Sufiks ABBABBBA redukuje prefikso-sufiks do A na pozycji 7.

Tablica П służy do wstępnej generacji właściwej tablicy BMNext. Na początku zerujemy wszystkie komórki tej tablicy. Następnie wyznaczamy kolejne wartości tablicy П. Jeśli prefikso-sufiks poprzedniego sufiksu wzorca nie może być rozszerzony w lewo na prefikso-sufiks sufiksu rozpoczynającego się na pozycji i-tej, to odnotowujemy ten fakt w elemencie BMNext [ pozycja prefikso-sufiksu ] o ile nie zawiera on już jakiejś wartości różnej od 0 (dotyczy to prefikso-sufiksu mniejszego sufiksu, który ma preferencje ). Do elementu tablicy BMNext wpisujemy różnicę pozycji nie rozszerzalnego prefikso-sufiksu oraz i, czyli:

BMNext [ pozycja prefikso-sufiksu ] = pozycja prefikso-sufiksu – pozycja sufiksu

W efekcie otrzymujemy wartość przesunięcie okna wzorca p w łańcuchu s, po którym zrównują się pozycje pasującego prefikso-sufiksu we wzorcu i w oknie. Prześledźmy teraz tworzenie obu tablic dla wzorca ABBABBBA:

Tworzenie tablic П i BMNext Opis 
     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A
     П: . . . . . . . . 9 
BMNext: 0 0 0 0 0 0 0 0 0
 Inicjujemy П [ 8 ] = 9, zerujemy BMNext 
     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A 
     П: . . . . . . . 8 9 
BMNext: 0 0 0 0 0 0 0 0 1
Na pozycji 7 jest sufiks A. Posiada on prefikso-sufiks pusty rozpoczynający się na pozycji 8. Prefikso-sufiks tego sufiksu nie daje się rozszerzyć w lewo.
W BMNext [ 8 ] wpisujemy 8 - 7 = 1		 
     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A 
     П: . . . . . . 8 8 9
BMNext: 0 0 0 0 0 0 0 0 1 
 Sufiks BA również posiada prefikso-sufiks pusty. Prefikso-sufiks nie jest rozszerzalny, ale w BMNext [ 8 ] już mamy wpis 1. 
     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A 
     П: . . . . . 8 8 8 9 
BMNext: 0 0 0 0 0 0 0 0 1 
 Sufiks BBA posiada prefikso-sufiks pusty i nie jest rozszerzalny.
Tablicy BMNext nie modyfikujemy.		 
     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A 
     П: . . . . 8 8 8 8 9 
BMNext: 0 0 0 0 0 0 0 0 1
Sufiks BBBA posiada prefikso-sufiks pusty i jest rozszerzalny.
Tablicy BMNext nie modyfikujemy.		 
     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A 
     П: . . . 7 8 8 8 8 9 
BMNext: 0 0 0 0 0 0 0 0 1
Sufiks ABBBA posiada prefikso-sufiks A rozpoczynający się na pozycji 7 i jest rozszerzalny.
Tablicy BMNext nie modyfikujemy.		 
     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A 
     П: . . 6 7 8 8 8 8 9 
BMNext: 0 0 0 0 0 0 0 0 1
Sufiks BABBBA posiada prefikso-sufiks BA rozpoczynającego się na pozycji 6 i jest rozszerzalny.
Tablicy BMNext nie modyfikujemy.		 
     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A 
     П: . 5 6 7 8 8 8 8 9 
BMNext: 0 0 0 0 0 4 0 0 1
Sufiks BBABBBA posiada prefikso-sufiks BBA rozpoczynającego się na pozycji 5 i nie jest rozszerzalny.
W BMNext [ 5 ] wpisujemy 5 - 1 = 4		 
     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A 
     П: 7 5 6 7 8 8 8 8 9 
BMNext: 0 0 0 0 0 4 0 0 1
 Sufiks ABBABBBA redukuje prefikso-sufiks do A na pozycji 7.

Algorytm etapu nr 1 tworzenia tablicy BMNext dla pełnego algorytmu Boyera-Moore'a

Wejście:

p  – wzorzec

Wyjście:

BMNext – tablica m  + 1 elementowa przesunięć okna wzorca, częściowo zapełniona, elementy BMNext  ∈ C
П – pomocnicza tablica m  + 1 elementowa położeń prefikso-sufiksów sufiksów wzorca, П  ∈ C

Zmienne pomocnicze:

i  –  indeksowanie elementów tablic, i  ∈ N
m  – długość wzorca p, m  ∈ N
b  – położenie prefikso-sufiksu aktualnego sufiksu, b  ∈ N

Lista kroków:

K01: m  ←  | p | wyznaczamy długość wzorca
K02: Dla i  = 0, 1, ..., m :
wykonuj BMNext [ i  ] ← 0		 zerujemy elementy tablicy BMNext
K03: i  ←  m ustawiamy indeks elementów dla tablicy П
K04: b  ← m  + 1 wstępne położenie prefikso-sufiksu poza pustym sufiksem
K05: П [ i  ] ←  b inicjujemy ostatni element tablicy
K06: Dopóki i  > 0,
wykonuj kroki K07...K12		 pętla wypełniająca komórki tablicy П
K07:     Dopóki ( b  ≤ m  ) obrazek ( p [ i-1 ] ≠ p [ b-1 ] ):
    wykonuj kroki K08...K09		 pętla obsługuje sytuację, gdy bieżący prefikso-sufiks istnieje i nie daje się rozszerzyć w lewo.
K08:         Jeśli BMNext [ b  ] = 0,
        to BMNext [ b  ] ← b  - i		 odnotowujemy taki prefikso-sufiks w tablicy BMNext o ile nie został już odnotowany przez wcześniejszy sufiks.
K09:         b  ← П [ b  ] w b umieszczamy położenie prefikso-sufiksu wewnętrznego i kontynuujemy pętlę K07
K10:     b  ← b  - 1 prefikso-sufiks jest rozszerzalny lub nie istnieje
K11:     i  ← i  - 1 przesuwamy się na kolejną pozycję w lewo.
K12:     П [ i  ]  ← b położenie prefikso-sufiksu zapamiętujemy w tablicy П'
K13: Zakończ  

Etap 2

Po zakończeniu etapu 1 otrzymujemy wypełnioną tablicę П, zawierającą położenia prefikso-sufiksów kolejnych sufiksów wzorca oraz częściowo wypełnioną tablicę BMNext zawierającą przesunięcia okna wzorca dla kolejnych sufiksów. W etapie 2 sprawdzamy, czy istnieje największy prefikso-sufiks wzorca zawarty w całości w pasującym sufiksie. Wzorzec można wtedy przesunąć tak daleko, jak pozwoli na to pasujący prefikso-sufiks:

obrazek

Dlatego wyznaczymy teraz dla każdego sufiksu najdłuższy prefikso-sufiks wzorca, który jest zawarty w tym sufiksie. Pozycja startowa najszerszego prefikso-sufiksu wzorca jest zawarta w П [ 0 ]. Dla naszego wzorca ABBABBBA jest to 7, ponieważ prefikso-sufiks A rozpoczyna się od pozycji 7:

     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A 
     П: 7 5 6 7 8 8 8 8 9 
BMNext: 0 0 0 0 0 4 0 0 1

Wartość ta zostaje umieszczona w kolejnych, wolnych elementach tablicy BMNext. Jednakże gdy sufiks wzorca stanie się krótszy od prefikso-sufiksu wzorca (czyli gdy go już nie może zawierać ), to kolejnym prefikso-sufiksem stanie się jego prefikso-sufiks wewnętrzny. W efekcie otrzymamy pełną tablicę BMNext:

     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A 
     П: 7 5 6 7 8 8 8 8 9 
BMNext: 7 7 7 7 7 4 7 7 1

Algorytm etapu nr 2 tworzenia tablicy BMNext dla pełnego algorytmu Boyera-Moore'a

Wejście:

p  – wzorzec
m  – długość wzorca (z poprzedniego etapu ), m  ∈ N
BMNext – tablica m  + 1 elementowa przesunięć okna wzorca częściowo zapełniona w etapie nr 1. BMNext  ∈ C
П – pomocnicza tablica m  + 1 elementowa położeń prefikso-sufiksów sufiksów wzorca, utworzona w etapie nr 1, П  ∈ C

Wyjście:

BMNext – kompletna tablica m  + 1 elementowa przesunięć okna wzorca

Zmienne pomocnicze:

i  – indeksowanie elementów tablic, i  ∈ N
b  – położenie prefikso-sufiksu aktualnego sufiksu, b  ∈ N

Lista kroków:

K01: b  ← П [ 0 ] najdłuższy prefikso-sufiks
K02: Dla i  = 0, 1, ..., m :
wykonuj kroki K03...K04		 indeksujemy kolejne komórki BMNext
K03:     Jeśli BMNext [ i  ] = 0,
    to BMNext [ i  ] ← b		 w wolnych elementach umieszczamy położenie prefikso-sufiksu
K04:     Jeśli i  = b,
    to b  ← П [ b  ]		 jeśli sufiks nie mieści prefikso-sufiksu, to bierzemy kolejny prefikso-sufiks
K05: Zakończ  
Na początek:  podrozdziału   strony 

Algorytm Boyera-Moore'a wyszukiwania wzorca

Algorytm BM składa się z etapu przetwarzania wzorca, w którym wyznacza się dwie tablice:

  1. Last zawierającą ostatnie położenia znaków alfabetu we wzorcu
  2. BMNext zawierającą przesunięcia dla pasujących sufiksów wzorca.

Po wyznaczeniu tych tablic następuje właściwy etap wyszukiwania.

Pełny algorytm Boyera-Moore'a wyszukiwania wzorca

Wejście:

s  – przeszukiwany łańcuch
p  – poszukiwany wzorzec
z p  – kod pierwszego znaku alfabetu.
z k – kod ostatniego znaku alfabetu

Wyjście:

Kolejne pozycje wystąpień wzorca w łańcuchu. Wartość -1 nie wskazuje żadnej pozycji wzorca i oznacza, iż wzorzec nie pojawia się w przeszukiwanym łańcuchu.

Zmienne pomocnicze:

i  –  położenie okna wzorca p  w przeszukiwanym łańcuchu s, i  ∈ N
j  – położenie porównywanego znaku we wzorcu p, j  ∈ N
m  – długość wzorca p  - wyznaczane w trakcie wyliczania tablic Last i BMNext, m  ∈ N
n  – długość łańcucha s  – wyznaczane w trakcie wyliczania tablic Last i BMNext, n  ∈ N
Last  – tablica ostatnich wystąpień znaków alfabetu we wzorcu p. Indeksy od 0 do z k  - z p. Last  ∈ C
BMNext  – tablica przesunięć okna wzorca dla pasujących sufiksów. Indeksy od 0 do m. BMNext  ∈ C
pp  – znalezione pozycje wzorca p  w łańcuchu s, pp  ∈ N
max ( a, b  )  – zwraca większą z liczb a  lub b

Lista kroków:

K01: Wyznacz tablicę Last
dla p, z p  i z k		 wyznaczamy ostatnie położenia znaków alfabetu we wzorcu
K02: Wyznacz tablicę BMNext
dla p		 wyznaczamy przesunięcia okna wzorca dla pasujących sufiksów
K03: pp  ← -1 ustawiamy pozycję wzorca na "nie znaleziono"
K04: i  ← 0 okno wzorca umieszczamy na początku łańcucha s
K05: Dopóki i  ≤ n  - m,
wykonuj kroki K06...K13		 dopóki okno wzorca mieści się wewnątrz łańcucha
K06:     j  ← m  - 1 porównywanie znaków wzorca z łańcuchem rozpoczynamy od końca
K07:     Dopóki ( j  > -1 ) obrazek ( p [ j  ] = s [ i + j  ] ),
    wykonuj j  ← j  - 1		 pętla wykonuje się, gdy pozycja j jest w obrębie wzorca oraz znak wzorca pasuje do znaku okna wzorca w łańcuchu s.
K08:     Jeśli j  = -1,
    to idź do kroku K11		 cały wzorzec pasuje do okna?
K09:     i  ← i  + max ( BMNext [ j  + 1 ], j  - Last [ kod ( s [ i  + j  ] ) - z p  ] ) jeśli nie, to pozycję okna wzorca zwiększamy o większe z przesunięć pasującego sufiksu lub  do ostatniej pozycji nie pasującego znaku
K10:     Następny obieg pętli K05  
K11:     pp  ← i tutaj jesteśmy, gdy wzorzec pasuje do okna
K12:     Pisz pp wyprowadzamy pozycję wzorca p w łańcuchu s
K13:     i  ← i  + BMNext [ 0 ] przesuwamy okno na następną możliwą pozycję i kontynuujemy
K14: Jeśli pp  = -1,
to pisz -1		 sprawdzamy, czy znaleziono pozycję wzorca. Jeśli nie, to wynik -1
K15: 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 79 znakowy łańcuch zbudowany z pseudolosowych kombinacji liter A i B oraz 5 znakowy wzorzec wg tego samego schematu. Następnie program wyznacza tablicę długości maksymalnych prefikso-sufiksów kolejnych prefiksów wzorca i wykorzystuje ją do znalezienia wszystkich wystąpień wzorca w łańcuchu.
Pascal
// Wyszukiwanie wzorca pełnym algorytmem BM
// Data:  10.06.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------------------

program prg;

uses Math;

const
  N  = 79;  // długość łańcucha s
  M  =  5;  // długość wzorca p
  zp = 65;  // kod pierwszego znaku alfabetu
  zk = 66;  // kod ostatniego znaku alfabetu

var
  s, p : ansistring;
  Last : array [ 0..zk-zp ] of integer;
  BMNext, Pi : array [ 0..M ] of integer;
  b, i, j, pp : integer;

begin
  randomize;

// generujemy łańcuch s

  s := '';
  for i := 1 to N do
    s := s + chr ( zp + random ( zk - zp + 1 ) );

// generujemy wzorzec p

  p := '';
  for i := 1 to M do
    p := p + chr ( zp + random ( zk - zp + 1 ) );

// wypisujemy wzorzec

  writeln ( p );

// wypisujemy łańcuch

  writeln ( s );

// dla wzorca obliczamy tablicę Last [ ] 

  for i := 0 to zk - zp do Last [ i ] := 0;
  for i := 1 to M do Last [ ord ( p [ i ] ) - zp ] := i;

// Etap I obliczania tablicy BMNext [ ] 

  for i := 0 to M do BMNext [ i ] := 0;
  i := M; b := M + 1; Pi [ i ] := b;
  while i > 0 do
  begin
    while( b <= M ) and ( p [ i ] <> p [ b ] ) do
    begin
      if BMNext [ b ] = 0 then BMNext [ b ] := b - i;
      b := Pi [ b ];
    end;
    dec ( b ); dec ( i ); Pi [ i ] := b;
  end;

// Etap II obliczania tablicy BMNext [ ] 

  b := Pi [ 0 ];
  for i := 0 to M do
  begin
    if BMNext [ i ] = 0 then BMNext [ i ] := b;
    if i = b then b := Pi [ b ];
  end;

// szukamy pozycji wzorca w łańcuchu

  pp := 1; i := 1;
  while i <= N - M + 1 do
  begin
    j := M;
    while( j > 0 ) and ( p [ j ] = s [ i = j - 1 ] ) do dec ( j );
    if j = 0 then
    begin
      while pp < i do
      begin
        write ( ' ' ); inc ( pp );
      end;
      write ( '^' ); inc ( pp );
      inc ( i, BMNext [ 0 ] );
    end
    else
      inc ( i, max ( BMNext [ j ], j-Last [ ord ( s [ i+j-1 ] )-zp ] ) );
  end;
  writeln;
end.
C++
// Wyszukiwanie wzorca pełnym algorytmem BM
// Data:  10.06.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------------------

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

using namespace std;

const int N  = 79;  // długość łańcucha s
const int M  =  5;  // długość wzorca p
const int zp = 65;  // kod pierwszego znaku alfabetu
const int zk = 66;  // kod ostatniego znaku alfabetu

int main( )
{
  string s, p;
  int Last [ zk - zp + 1 ], BMNext [ M + 1 ], Pi [ M + 1 ], b, i, j, pp;

  srand ( ( unsigned )time ( NULL ) );

// generujemy łańcuch s

  s = "";
  for( i = 0; i < N; i++ )
    s += zp + rand( ) % ( zk - zp + 1 );

// generujemy wzorzec p

  p = "";
  for( i = 0; i < M; i++ )
    p += zp + rand( ) % ( zk - zp + 1 );

// wypisujemy wzorzec

  cout << p << endl;

// wypisujemy łańcuch

  cout << s << endl;

// dla wzorca obliczamy tablicę Last [ ] 

  for( i = 0; i <= zk - zp; i++ ) Last [ i ] = -1;
  for( i = 0; i < M; i++ ) Last [ p [ i ] - zp ] = i;

// Etap I obliczania tablicy BMNext [ ] 

  for( i = 0; i <= M; i++ ) BMNext [ i ] = 0;
  i = M; b = M + 1; Pi [ i ] = b;
  while( i > 0 )
  {
    while( ( b <= M ) && ( p [ i - 1 ] != p [ b - 1 ] ) )
    {
      if( BMNext [ b ] == 0 ) BMNext [ b ] = b - i;
      b = Pi [ b ];
    }
    Pi [ --i ] = --b;
  }

// Etap II obliczania tablicy BMNext [ ] 

  b = Pi [ 0 ];
  for( i = 0; i <= M; i++ )
  {
    if( BMNext [ i ] == 0 ) BMNext [ i ] = b;
    if( i == b ) b = Pi [ b ];
  }

// szukamy pozycji wzorca w łańcuchu

  pp = i = 0;
  while( i <= N - M )
  {
    j = M - 1;
    while( ( j > -1 ) && ( p [ j ] == s [ i + j ] ) ) j--;
    if( j == -1 )
    {
      while( pp < i )
      {
        cout << " "; pp++;
      }
      cout << "^"; pp++;
      i += BMNext [ 0 ];
    }
    else i += max ( BMNext [ j+1 ], j-Last [ s [ i+j ] -zp ] );
  }
  cout << endl;
  return 0;
}
Basic
' Wyszukiwanie wzorca pełnym algorytmem BM
' Data:  10.06.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------------------

Const N  = 79  ' długość łańcucha s
Const M  =  5  ' długość wzorca p
Const zp = 65  ' kod pierwszego znaku alfabetu
Const zk = 66  ' kod ostatniego znaku alfabetu

' Funkcja wyznacza większą z dwóch liczb
'---------------------------------------
Function max ( Byval a As Integer, Byval b As Integer ) As Integer
  If a > b Then max = a Else max = b
End Function

Dim As String s, p
Dim As Integer Last ( zk - zp ), BMNext ( M ), Pi ( M ), b, i, j, pp

Randomize

' generujemy łańcuch s

s = ""
For i = 1 To N: s += Chr ( zp + Cint ( Rnd * ( zk - zp ) ) ): Next

' generujemy wzorzec p

p = ""
For i = 1 To M: p += Chr ( zp + Cint ( Rnd * ( zk - zp ) ) ): Next

' wypisujemy wzorzec

Print p

' wypisujemy łańcuch

Print s

' dla wzorca obliczamy tablicę Last [ ] 

For i = 0 To zk - zp: Last ( i ) = 0: Next
For i = 1 To M: Last ( Asc ( Mid ( p, i, 1 ) ) - zp ) = i: Next

' Etap I obliczania tablicy BMNext [ ] 

For i = 0 To M: BMNext ( i ) = 0: Next
i = M: b = M + 1: Pi ( i ) = b
While i > 0
  while( b <= M ) And ( Mid ( p, i, 1 ) <> Mid ( p, b, 1 ) )
    If BMNext ( b ) = 0 Then BMNext ( b ) = b - i
    b = Pi ( b )
  Wend
  b -= 1: i -= 1: Pi ( i ) = b
Wend

' Etap II obliczania tablicy BMNext [ ] 

b = Pi ( 0 )
For i = 0 To M
  If BMNext ( i ) = 0 Then BMNext ( i ) = b
  If i = b Then b = Pi ( b )
Next

' szukamy pozycji wzorca w łańcuchu

pp = 1: i = 1
While i <= N - M + 1
  j = M
  while( j > 0 ) And ( Mid ( p, j, 1 ) = Mid ( s, i + j - 1, 1 ) ): j -= 1: Wend
  If j = 0 Then
    While pp < i
      Print " ";: pp += 1
    Wend
    Print "^";: pp += 1
    i += BMNext ( 0 )
  Else
    i += max ( BMNext ( j ), j - Last ( Asc ( Mid ( s, i + j - 1, 1 ) ) - zp ) )
  End If
Wend
Print
End
Wynik:
ABBBA
BBAABBBAABBBAABAAABBBABBBAAABABBAAABBAAAABBABAAABBAABAABBBBBBBBAABABBAAABAAAABB
   ^    ^        ^   ^
Wyszukiwanie wzorca pełnym algorytmem BM
 (C)2020 mgr Jerzy Wałaszek

...
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
©2023 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.