Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytmy i struktury danych

(7) Wyszukiwanie wzorców

Paweł J. Matuszyk

AGH Kraków

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Plan wykładu

1

Wst ˛ep

2

Algorytm naiwny

3

Algorytm Rabina-Karpa

4

Algorytm Knutha-Morrisa-Pratta

Konstrukcja tablicy pomocniczej S

5

Algorytm Boyer-Moore’a

Idea metody
Konstrukcja tablicy

bcs

Konstrukcja tablicy

gcs

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Problem wyszukiwania wzorca

Problem wyszukiwania wzorca

Dana jest tablica T o długo´sci n oraz wzorzec P (równie˙z
tablica) o długo´sci m 6 n.
Zakładamy, ˙ze elementami tablic s ˛

a symbole nale˙z ˛

ace do

sko ´nczonego alfabetu Σ.

Mówimy, ˙ze wzorzec P wyst ˛epuje w tek´scie T z
przesuni ˛eciem s, je´sli wzorzec wyst ˛epuje w tek´scie
pocz ˛

awszy od pozycji s.

T [s . . . s + m − 1] = P[0 . . . m − 1]

0 6 s 6 n − m.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Problem wyszukiwania wzorca

Zastosowania:

Edytory tekstów.

Przegl ˛

adarki dokumentów.

Przegl ˛

adarki internetowe.

Dopasowanie sekwencji DNA.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Plan wykładu

1

Wst ˛ep

2

Algorytm naiwny

3

Algorytm Rabina-Karpa

4

Algorytm Knutha-Morrisa-Pratta

Konstrukcja tablicy pomocniczej S

5

Algorytm Boyer-Moore’a

Idea metody
Konstrukcja tablicy

bcs

Konstrukcja tablicy

gcs

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm naiwny

Przesuwamy nad tekstem okienko o rozmiarze m i
sprawdzamy taki wycinek z wzorcem.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm naiwny

int

naive_match(

const char

* T,

int

n,

const char

* P,

int

m) {

for

(

int

s = 0, end = n - m, i; s < end; ++s) {

for

(i = 0; i < m && T[s + i] == P[i]; ++i);

if

(i == m)

return

s;

}

return

-1;

}

Zło˙zono´s´c obliczeniowa:

O ((n − m + 1)m)

.

Algorytm nie jest optymalny, bo informacja o tek´scie
uzyskana dla jednej warto´sci s jest całkowicie ignorowana
dla kolejnej warto´sci s.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Plan wykładu

1

Wst ˛ep

2

Algorytm naiwny

3

Algorytm Rabina-Karpa

4

Algorytm Knutha-Morrisa-Pratta

Konstrukcja tablicy pomocniczej S

5

Algorytm Boyer-Moore’a

Idea metody
Konstrukcja tablicy

bcs

Konstrukcja tablicy

gcs

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Rabina-Karpa

Pomysł: unika´c sprawdzania dopasowania całego wzorca

do okienka, kiedy mo˙zna szybciej stwierdzi´c, ˙ze dane dwa

ci ˛

agi nie pasuj ˛

a.

Wykorzystujemy funkcj ˛e mieszaj ˛

ac ˛

a h i porównujmy

najpierw h(P) z h(T [s . . . s + m − 1]):

je˙zeli funkcje nie s ˛

a równe, zwi ˛ekszamy s

je˙zeli funkcje s ˛

a równe, porównujemy ci ˛

agi, jak w

algorytmie naiwnym.

Warunek: funkcja mieszaj ˛

aca h musi by´c prosta do

policzenia, tzn. maj ˛

ac obliczone h(T [s . . . s + m − 1])

mo˙zna bardzo prosto policzy´c h(T [s + 1 . . . s + m]).

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Rabina-Karpa

Zakładamy, ˙ze alfabet składa si ˛e z cyfr Σ = {0, 1, . . . , 9}.

A zatem ka˙zdy m-elementowy napis Q jest liczb ˛

a zapisan ˛

a w

systemie o podstawie d = 10.

Przyjmujemy, ˙ze h(Q) = warto´s´c liczby Q; wtedy, maj ˛

ac cyfry

mo˙zna obliczy´c warto´s´c tej liczby u˙zywaj ˛

ac

schematu Hornera

(zło˙zono´s´c Θ(m)):

h(Q) = Q[m − 1] + d (Q[m − 2] + . . . + d (Q[1] + dQ[0]))

Maj ˛

ac policzon ˛

a warto´s´c h

s

=

h(T [s . . . s + m − 1]):

h

s

=

T [s + m − 1] + d (T [s + m − 2] + . . . + d (T [s + 1] + dT [s]))

mo˙zna łatwo policzy´c h

s+1

=

h(T [s + 1 . . . s + m]):

h

s+1

=

d h

s

− d

m−1

T [s + 1]

+ T [s + m]

⇒

O(1)

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Rabina-Karpa

Trudno´s´c: dla du˙zych m (= długi wzorzec), liczby h(Q) oraz h

s

mog ˛

a zby´c du˙ze.

Rozwi ˛

azanie: obliczamy h(Q) i h

s

modulo q

— musimy jedynie

dobra´c odpowiedni ˛

a warto´s´c q.

⇒

Zazwyczaj wybiera si ˛e q tak ˛

a liczb ˛e pierwsz ˛

a, ˙ze dq mie´sci si ˛e

w słowie komputera, co pozwala wykonywa´c obliczenia w
arytmetyce pojedynczej precyzji.

Oczywi´scie z

h(Q) mod q = h

S

mod q

nie wynika równo´s´c

h(Q) = h

s

,

ale z

ró˙zno´sci

warto´sci modulo wynika ró˙zno´s´c h(Q) i h

s

.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Rabina-Karpa

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm naiwny

int

RK_match(

char

* T,

int

n,

char

* P,

int

m,

int

q,

int

d) {

int

c = pow(10, m - 1) % q;

// O(lg m)

int

p = 0, t = 0;

// kod wzorca i okienka tekstu

for

(

int

i = 0; i < m; ++i) {

// O(m)

p = (d * p - P[i]) % q;
t = (d * t - T[i]) % q;

}

// O(n)

for

(

int

s = 0, end = n - m, i; s < end; ++s) {

if

(p == s) {

// tylko a razy(!)

for

(i = 0; i < m && T[s + i] == P[i]; ++i);

// O(m)

if

(i == m)

return

s;

}

t = (d * (t - T[s+1] * c) + T[s+m]) % q;

// O(1)

}

}

Zło˙zono´s´c ´srednia: O ((n − m + 1) + am) =

O(n + m)

.

Zło˙zono´s´c pesymistyczna:

O ((n − m + 1)m)

.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Plan wykładu

1

Wst ˛ep

2

Algorytm naiwny

3

Algorytm Rabina-Karpa

4

Algorytm Knutha-Morrisa-Pratta

Konstrukcja tablicy pomocniczej S

5

Algorytm Boyer-Moore’a

Idea metody
Konstrukcja tablicy

bcs

Konstrukcja tablicy

gcs

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Knutha-Morrisa-Pratta

Obserwacja:

w przypadku wyst ˛

apienia niezgodno´sci na pozycji s + i, słowo

samo w sobie zawiera wystarczaj ˛

ac ˛

a ilo´s´c informacji, by

okre´sli´c gdzie powinno zacz ˛

a´c si ˛e kolejne dopasowanie (czyli

nowe s), zatem pomijaj ˛

ac ponown ˛

a analiz ˛e uprzednio

dopasowanych znaków.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Knutha-Morrisa-Pratta

Idea metody

s: 01234567890123456789012

T: ABC ABCDAB ABCDABCDABDE

|

P: ABCDABD

i: 0123456

Mamy niedopasowanie dla s = 0 i i = 3.

Zamiast rozpoczyna´c nowe poszukiwanie od s = 1
zapami ˛etujemy, ˙ze ˙zadne

A

nie wyst ˛

apiło mi ˛edzy pozycj ˛

a 0

i 3 z wyj ˛

atkiem pozycji 0.

⇒

nie ma mo˙zliwo´sci dopasowania wzorca sprawdzaj ˛

ac od

pozycji s = 1 . . . 3.

⇒

Zaczniemy poszukiwanie od s = 4.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Knutha-Morrisa-Pratta

Idea metody

s: 01234567890123456789012

T: ABC ABCDAB ABCDABCDABDE

|

P:

ABCDABD

i:

0123456

Mamy niedopasowanie dla s = 4 i i = 6.

Przed ko ´ncem bie˙z ˛

acego dopasowania cz ˛

astkowego,

przeszli´smy przez

AB

, które mogłoby by´c pocz ˛

atkiem

nowego dopasowania, wi ˛ec musimy wzi ˛

a´c je pod uwag ˛e.

⇒

Zaczynamy nowe poszukiwanie od pozycji s = 8 i i = 2.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Knutha-Morrisa-Pratta

Idea metody

s: 01234567890123456789012

T: ABC ABCDAB ABCDABCDABDE

|

P:

ABCDABD

i:

0123456

Mamy niedopasowanie dla s = 8 i i = 2.

Mamy od razu niezgodno´s´c.

Wzorzec nie zawiera spacji, wi ˛ec wracamy na pocz ˛

atek P.

⇒

Zaczynamy nowe poszukiwanie od pozycji s = 11 i i = 0.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Knutha-Morrisa-Pratta

Idea metody

s: 01234567890123456789012

T: ABC ABCDAB ABCDABCDABDE

|

P:

ABCDABD

i:

0123456

Mamy niedopasowanie dla s = 11 i i = 6.

Przed ko ´ncem bie˙z ˛

acego dopasowania cz ˛

astkowego,

przeszli´smy przez

AB

, które mogłoby by´c pocz ˛

atkiem

nowego dopasowania, wi ˛ec musimy wzi ˛

a´c je pod uwag ˛e.

⇒

Zaczynamy nowe poszukiwanie od pozycji s = 15 i i = 2.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Knutha-Morrisa-Pratta

Idea metody

s: 01234567890123456789012

T: ABC ABCDAB ABCDABCDABDE

|

P:

ABCDABD

i:

0123456

Mamy dopasowanie dla s = 15.

Potrzebna jest pewna funkcja (tablica) pomocnicza S
(obliczana na pocz ˛

atku dla wzorca P), która wskazuje gdzie

musimy szuka´c pocz ˛

atku nowego dopasowania w przypadku,

gdy bie˙z ˛

ace zako ´nczy si ˛e brakiem dopasowania.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Knutha-Morrisa-Pratta

Idea metody

s: 01234567890123456789012

T: ABC ABCDAB ABCDABCDABDE

|

P:

ABCDABD

i:

0123456

Mamy dopasowanie dla s = 15.

Potrzebna jest pewna funkcja (tablica) pomocnicza S
(obliczana na pocz ˛

atku dla wzorca P), która wskazuje gdzie

musimy szuka´c pocz ˛

atku nowego dopasowania w przypadku,

gdy bie˙z ˛

ace zako ´nczy si ˛e brakiem dopasowania.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Konstrukcja tablicy pomocniczej S

Wpisy w S s ˛

a takie, ˙ze

je˙zeli mamy zaczynaj ˛

ace si ˛e w T [s] dopasowanie, które

zawiedzie gdy porównamy T [s + i] do P[i], wtedy nast ˛epne
mo˙zliwe dopasowanie rozpocznie si ˛e w indeksie

s + i − S[i]

w T

⇒

S[i] jest ilo´sci ˛

a kroków wstecz, które musimy wykona´c, gdy

nie istnieje dopasowanie

.

Implikacje:

⇒

S[0] = −1

oznacza, ˙ze je´sli P[0] nie zostanie dopasowane,

nie mo˙zemy si ˛e cofn ˛

a´c i musimy po prostu sprawdzi´c

nast ˛epny znak (zacz ˛

a´c od s = s + 1),

⇒

pomimo, ˙ze kolejne mo˙zliwe dopasowanie rozpocznie si ˛e
w indeksie

s + i − S[i]

, jak w powy˙zszym przykładzie, nie

musimy po tym wła´sciwie sprawdza´c ˙zadnego znaku w
S[i], wi ˛ec kontynuujemy szukanie od

P[S[i]]

.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Konstrukcja tablicy pomocniczej S

abab
| {z }

prefiks

aba

sufiks

bca

|{z}

Przez P

i

oznaczamy

prefiks

P o długo´sci i.

Dla danego wzorca P okre´slamy

tablic ˛e prefiksow ˛

a

S

nast ˛epuj ˛

aco:

S : {0, . . . , m − 1} → {−1, . . . , m − 2}

S[i] = max {k : k < i ∧ P

k

jest sufiksem P

i

} − 1

tzn. S[i] jest długo´sci ˛

a najdłu˙zszego prefiksu wzorca P

b ˛ed ˛

acego wła´sciwym sufiksem P

i

pomniejszon ˛

a o 1.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Konstrukcja tablicy pomocniczej S

i

0

1

2

3

4

5

6

7

8

9

P[i] a

b

a

b

a

b

a

b

c

a

S[i] −1 −1 0

1

2

3

4

5

−1 0

P[7]

a b

a b a b a b

c a

P[5]

a b a b a b

a b c a

S[7] = 5

P[3]

a b a b

a b a b c a

S[5] = 3

P[1]

a b

a b a b a b c a

S[3] = 1

P[−1]

a b a b a b a b c a

S[1] = −1

Przesuwamy sukcesywnie P w prawo i wynotowujemy sytuacje,
kiedy pewien prefiks P

k

pokrywa si ˛e z wła´sciwym prefiksem P

7

⇒ {6, 4, 2, 0}

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Konstrukcja tablicy pomocniczej S

vector<

int

> KMP_generate(

const char

* P,

int

m) {

vector<

int

> S(m);

S[0] = -1;

// P[k+1] to potencjalny kandydat podciagu

for

(

int

i = 1, k = -1; i < m; ++i) {

while

(k > -1 && P[k + 1] != P[i])

k = S[k];

if

(P[k + 1] == P[i])

// jeszcze nie koniec

++k;

S[i] = k;

}

return

S;

}

Zło˙zono´s´c obliczeniowa:

Θ(

m)

.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Knutha-Morrisa-Pratta

int

KMP_match(

const char

* T,

int

n,

const char

* P,

int

m) {

vector<

int

> S(KMP_generate(P, m));

for

(

int

s = 0, end = n - m + 1, i = 0; s < end;) {

for

(i = S[i] + 1; i < m && P[i] == T[s + i]; ++i);

//i = S[i] + 1;

//while(i < m && P[i] == T[s + i])

//

++i;

if

(i == m)

return

s;

s += max(0, i - S[i])

}

}

Zło˙zono´s´c obliczeniowa:

Θ(

n)

.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Plan wykładu

1

Wst ˛ep

2

Algorytm naiwny

3

Algorytm Rabina-Karpa

4

Algorytm Knutha-Morrisa-Pratta

Konstrukcja tablicy pomocniczej S

5

Algorytm Boyer-Moore’a

Idea metody
Konstrukcja tablicy

bcs

Konstrukcja tablicy

gcs

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Boyer-Moore’a

Idea metody

Skanowanie w celu dopasowania wzorca odbywa si ˛e od
prawej strony wzorca.
W przypadku niespasowania danego znaku b ˛

ad´z

dopasowania całego wzorca stosuje si ˛e dwie funkcje z
wcze´sniej wyliczonymi warto´sciami:

good_suffix_shift
bad_character_shift

W algorytmie stosujemy zawsze maksymaln ˛

a warto´s´c

wynikaj ˛

ac ˛

a z good_suffix_shift oraz bad_character_shift.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Boyer-Moore’a

Idea metody

Omówimy poni˙zej cztery sytuacje, zakładaj ˛

ac co

nast ˛epuje:

W danym kroku działania algorytmu, cz ˛e´s´c wzorca P i
tekstu T zaznaczona jako u (wielkie litery!) pasuje do
siebie.
Na kolejnej pozycji (a) wyst ˛epuje ró˙znica.
W zale˙zno´sci od sytuacji mo˙zemy przesun ˛

a´c si ˛e w

poszukiwaniu o ró˙zn ˛

a warto´s´c — przykłady poni˙zej.

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Boyer-Moore’a

Idea metody

Je˙zeli wzorzec P zawiera w sobie kolejne wyst ˛

apienie u to

przesuwamy P tak aby u pokrywało si ˛e z tekstem.

U˙zywamy good_suffix_shift.

T: cccccccBBAbbaababbacc

P:

abbaaBBA

|

T: cccccccBBAbbaababbacc

P:

aBBAabba

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Boyer-Moore’a

Idea metody

Je˙zeli wzorzec P nie zawiera w sobie kolejnego
wyst ˛

apienia u to przesuwamy P tak by jego suffiks

spasował si ˛e maksymalnie z jego dotychczas spasowanym
prefiksem v .
U˙zywamy good_suffix_shift.

T: cccccBBAbbaababbacc

P:

baaBBA

|

T: cccccbBAbbaababbacc

P:

BAabba

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Boyer-Moore’a

Idea metody

Przesuwamy P tak aby pierwszy znak od prawej w P
spasował si ˛e z aktualnie rozpatrywanym znakiem w
tek´scie (czyli z a).
U˙zywamy bad_character_shift.

T: cccccccBBAbbaababbacc

P:

cbcaaBBA

|

T: ccccccCbbabbaababbacc

P:

cbCaabba

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Boyer-Moore’a

Idea metody

(Przesuwamy P tak aby pierwszy znak od prawej w P
spasował si ˛e z aktualnie rozpatrywanym znakiem w T .)
Je˙zeli takiego znaku nie ma to ustawiamy koniec wzorca
bezpo´srednio za nim.
U˙zywamy bad_character_shift.

T: cccccceBBAbbaababbacc

P:

cbcaaBBA

|

T: ccccccebbabbaababbacc

P:

cbcaabba

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Konstrukcja tablicy bad_character_shift

Warto´sci funkcji bad_character_shift przechowywane s ˛

a w

tablicy

bcs

o rozmiarze alfabetu (poniewa˙z skok zale˙zy od

warto´sci niedopasowanego znaku).
Dla ka˙zdego znaku x wynosi ona:

bcs(x ) =



min {i : 0 < i 6 m − 1} je˙zeli P[m − 1 − i] = x

m

dla pozostałych znaków

Uwaga: ostatni znak wzorca P traktowany inaczej!
Przykład:

m = 7

bcs[c]

= 4

i:

0123456

bcs[b]

= 1

P:

abcdabc

bcs[a]

= 2

bcs[d]

= 3

bcs[e..z] = 7

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Konstrukcja tablicy bad_character_shift

vector<

int

>

calcBCS(

char

* P,

int

m,

int

alfSize) {

vector<

int

>

bcs(alfSize);

// max shift dla wszystkich znaków

for

(

int

i = 0; i < alfSize; i++)

bcs[i] = m;

// min shift dla znaków wzorca P

for

(

int

i = 0, end = m - 1; i < end; ++i)

bcs[P[i]] = end - i;

return

bcs;

}

Zło˙zono´s´c obliczeniowa:

Θ(|Σ| +

m − 1)

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Konstrukcja tablicy good_character_shift

Warto´sci funkcji good_character_shift przechowywane s ˛

a

w tablicy

gcs

o rozmiarze m.

Je˙zeli na pozycji i wyst ˛

apiło niedopasowanie, to:

gcs(x ) =















min {i − k : 0 < k 6 i ∧

P[k + 1..m − i − 1 + k ] = P[i + 1..m − 1] ∧ P[i] 6= P[k ]} lub

min {i + k : 0 < k 6 m − i ∧

P[i + k ..m − 1] = P[m − i − k ..m − 1]}

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Konstrukcja tablicy good_character_shift

vector<

int

> calcGCS(

char

* P,

int

m) {

vector<

int

>

gcs(m), f(m);

for

(

int

i = 0; i < m; i++) gcs[i] = 0;

int

i = m - 1;

for

(

int

j = m - 1; j >= 0; --j, --i)

f[j] = i + 1;

while

(i < m && P[j] != P[i]) {

if

(gcs[i] == 0)

gcs[i] = i - j;

i = f[i] - j;

}

}

for

(

int

j = 0; j < m; ++j) {

if

(gcs[j] == 0)

gcs[j] = i + 1;

if

(j == i)

i = f[i] - j;

}

return

gcs;

}

Zło˙zono´s´c obliczeniowa:

O(m)

Wst ˛ep

Algorytm naiwny

Algorytm Rabina-Karpa

Algorytm Knutha-Morrisa-Pratta

Algorytm Boyer-Moore’a

Algorytm Boyer-Moore’a

int

BM_match(

char

* T,

int

n,

char

* P,

int

m,

int

alfSize) {

vector<

int

> bcs(calcBCS(P, m, alfSize));

vector<

int

> gcs(calcGCS(P, m));

for

(

int

s = 0, end = n - m, i; s < end;) {

for

(i = m - 1; i >= 0 && P[i] == T[s + i]; --i);

if

(i == 0)

return

s;

else

s += max(gcs[i], bgs[T[s + i]] + i - m + 1);

}

return

-1;

}

Zło˙zono´s´c obliczeniowa najgorszego przypadku:

O((n + m − 1)m + |Σ|)