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

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

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

SPIS TREŚCI W KONSERWACJI
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
П: . . . . . . . . 
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 
     p: A B B A B B B A
     П: . . . . . . . .
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
zp – 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 zk - zp. 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, zp i zk
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 <ctime>

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(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
©2024 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.