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


Tematy pokrewne   Podrozdziały
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
  Heurystyki algorytmu Boyera-Moore'a
Tworzenie tablicy przesunięć BMNext
Algorytm Boyera-More'a wyszukiwania wzorca

 

Problem

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


Tutaj znajdziesz oryginalny tekst R.S.Boyera oraz J.S.Moore'a z roku 1977.

 

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:

 

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.

 

 

  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:

 

 

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 duże 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ęć.

 

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

 

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. ednocześ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 
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, BMNext C
П – pomocnicza tablica m + 1 elementowa położeń prefikso-sufiksów sufiksów wzorca, П C
Elementy 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: bm + 1 ; wstępne położenie prefikso-sufiksu poza pustym sufiksem
K05: П[i] ← b ; inicjujemy ostatni element tablicy
K06: Dopóki i > 0, wykonuj K07...K12 ; pętla wypełniająca komórki tablicy П
K07:     Dopóki (bm) (p[i-1] ≠ p[b-1]) wykonuj 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:     bb - 1 ; prefikso-sufiks jest rozszerzalny lub nie istnieje
K11:     ii - 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:

 

 

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
Elementy 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 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  

 

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.
zk – 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.

Elementy 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 K06...K13 ; dopóki okno wzorca mieści się wewnątrz łańcucha
K06:     jm - 1 ; porównywanie znaków wzorca z łańcuchem rozpoczynamy od końca
K07:     Dopóki (j > -1) (p[j] = s[i+j]), wykonuj jj - 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 K11 ; cały wzorzec pasuje do okna?
K09:     ii + max(BMNext[j + 1], j - Last[kod(s[i + j]) - zp]) ; 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:     ppi ; tutaj jesteśmy, gdy wzorzec pasuje do okna
K12:     Pisz pp ; wyprowadzamy pozycję wzorca p w łańcuchu s
K13:     ii + 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  

 

Program

Ważne:

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 80 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.

 

Lazarus
// Wyszukiwanie wzorca pełnym algorytmem BM
// Data:  10.06.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------------------

program prg;

uses Math;

const
  N  = 80;  // 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

  write(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.
Code::Blocks
// Wyszukiwanie wzorca pełnym algorytmem BM
// Data:  10.06.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------------------

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

using namespace std;

const int N  = 80;  // 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;

// 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;
}
Free Basic
' Wyszukiwanie wzorca pełnym algorytmem BM
' Data:  10.06.2008
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------------------

Const N  = 80  ' 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
BBAABBBAABBBAABAAABBBABBBAAABABBAAABBAAAABBABAAABBAABAABBBBBBBBAABABBAAABAAAABBB
   ^    ^        ^   ^

 

Wyszukiwanie wzorca pełnym algorytmem BM
(C)2012 mgr Jerzy Wałaszek


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.