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
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
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
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));
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
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.
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 + |Σ|)