Zaawansowane algorytmy i struktury danych/Wykład 1: Różnice pomiędzy wersjami

Aktualna wersja na dzień 22:14, 11 wrz 2023

Zaawansowane algorytmy tekstowe I

Algorytmy tekstowe są istotne w wielu dziedzinach informatyki, jak na przykład w edytorach tekstowych lub wyszukiwarkach. Tekst jest naturalnym typem informacji.

Formalnie tekst jest ciągiem symboli. Przyjmujemy, że jest on zadany tablicą $x [1 . . k]$ , elementami której są symbole. Liczba $k = | x |$ jest długością (rozmiarem) tekstu. W większości naszych algorytmów jedyne operacje dopuszczalne na symbolach wejściowych to porównania dwóch symboli.

Podstawowym problemem tekstowem jest problem string matchingu, polegający na szukaniu wzorca $x = x [1 . . m]$ w tekście $y = y [1 . . n]$ . Elementami tablic są symbole. Na kursie z ASD przerabialiśmy algorytm Knutha-Morrisa-Pratt(w skrócie KMP) i jego wariacje. Zaprezentujemy bardziej zaawansowany algorytm dla tego problemu: algorytm Boyera-Moore'a (w skrócie BM). Pomimo tego, że jest jasne jak ten algorytm działa, to jednak jego pełna analiza (złożoność, preprocessing) jest zawansowana.

Algorytm Boyera-Moore'a

Algorytm przykłada $x$ do tekstu $y$ startując od pozycji $i$ -tej w $y$ . Sprawdzamy, czy $x [1 . . m] = y [i + 1 . . i + m]$ . Pozycja $i$ wędruje ze strony lewej do prawej. Jednakże, w przeciwieństwie do algorytmu KMP, równość $x [1 . . m] = y [i + 1 . . i + m]$ sprawdzamy od strony prawej do lewej. Zaczniemy od algorytmu naiwnego.

Algorytm Naiwny-BM

$i : = 0;$
'while $i < n - m$ do
    $j : = m$ ,br>    while $j > 0$ and $x [j] = y [i + j]$ do $j : = j - 1$
   if $j = 0$ then return true;
   {zachodzi niezmiennik $(i, j)$ } $i : = i + 1$
return false;

Jeśli zachodzi równość, to stwierdzamy, że znaleźliśmy wystąpienie $x$ i kończymy. W przeciwnym razie mamy niezmiennik:

n i e z m i e n n i k (i, j) : x [j + 1 . . m] = y [i + j + 1 . . i + m]

oraz

x [j] \neq y [i + j]

.

Korzystając z niezmiennika liczymy przesunięcie większe niż 1. Przesunięcie $s$ jest bezpieczne, gdy jesteśmy pewni, że w każdej sytuacji pomiędzy $i$ oraz $i + s$ nie zaczyna się żadne wystąpienie wzorca $x$ w tekście $y$ . Przypuśćmy, że $x$ zaczyna od pozycji $i + s$ (zobacz Rysunek 1, gdzie jest przedstawiony przypadek $s < j$ .)

Zachodzi wtedy następujący warunek:

warunek1(j,s): dla każdego k

j < k \leq m \Rightarrow s > k

lub

x [k - s] = x [k]

,

warunek2(j,s): $s < j \Rightarrow x [j - s] \neq x [j]$ { własność niezgodności }.

Rysunek 1: Przesunięcie w algorytmie BM. Przypadek gdy

s = B M S h i f t [j] < j

.

Definiujemy dwa rodzaje przesunięć. Każde z nich dotyczy sufiksu wzorca zaczynającego się od pozycji $j < m$ .

$B M S h i f t^{'} [j] = \min {s > 0 : w a r u n e k 1 (j, s)}$

$B M S h i f t [j] = \min {s > 0 : w a r u n e k 1 (j, s) oraz w a r u n e k 2 (j, s)}$ .

Definiujemy również

B M S h i f t^{'} [m] = B M S h i f t [m] = m - P [m] = p e r i o d (x)

.

Algorytm {BM} jest wersją algorytmu Naiwny-BM, w którym przeunięcie $i$ o jeden zamieniamy na przesunięcie o $B M S h i f t [j]$ , zobacz Rysunek 2.

Algorytm BM

$i : = 0$
while $i < n - m$ do
    $j : = m$ ;    while $j > 0$ and $x [j] = y [i + j]$ do $j : = j - 1$ ;
   if $j = 0$ then return true;
   { $n i e z m i e n n i k (i, j)$ \} $i : = i + B M S h i f t [j]$ ;
return false;

Udowodnimy potem, że algorytm ten ma złożoność liniową. Jednakże w przeciwieństwie do łatwej analizy algorytmu KMP, w tym przypadku analiza jest skomplikowana. Mamy tu przykład algorytmu, którego poprawność jest dosyć oczywista, a analiza kosztu jest nietrywialna.

Rysunek 2: Historia algorytmu BM na przykładowych tekstach

x, y

.

Rysunek 3: Działanie dwóch wersji algorytmu BM na przykładowych tekstach. Algorytm BM stosujący przesunięcie

B M S h i f t^{'}

wykonuje 30 porównań symboli więcej (rysunek z lewej strony) niż normalny algorytm BM stosujący tablicę BM (rysunek prawej strony).

Algorytm BM ze słabszą tablicą przesunięć

Jeśli zastąpimy tablicę $B M S h i f t$ przez $B M S h i f t^{'}$ , wówczas czas algorytmu BM staje się kwadratowy. Przykładem tekstów, dla których osiągana jest wtedy złożoność kwadratowa są:

x = c a (b a)^{k} oraz y = a^{2 . k + 2} (b a)^{k}

.

Pozostawiamy jako ćwiczenie podanie wzoru na liczbę porównań z tablicą $B M S h i f t^{'}$ dla tych tekstów.

Różnica między $B M S h i f t$ i $B M S h i f t^{'}$ wydaje się być podobna do tej między silnymi prefikso-sufiksami i prefikso-sufiksami w algorytmie KMP. W obu przypadkach różnica sprowadza się do wykorzystania jednego bitu informacji, niezgodności dwóch symboli. Podczas gdy nie robi to istotnej różnicy w pesymistycznej złożoności algorytmu KMP, w tym przypadku jest to znacząca różnica między czasem kwadratowym i liniowym. Porównajmy działanie algorytmu z przesunięciem $B M S h i f t^{'}$ i of $B M S h i f t$ na tekstach(patrz rysunek)

x = c a b a b a b a b a

oraz

y = a a a a a a a a a a b a b a b a b a

.

Pewna własność kombinatoryczna tekstów

Okresem tekstu $x$ jest każda niezerowa liczba naturalna $p$ taka, że $x [i] = x [i + p]$ dla każdego $i$ , dla którego obie strony są zdefiniowane. Przez $p e r i o d (x)$ oznaczmy minimalny okres $x$ . Okres jest \mathit{ pełny} gdy jest dzielnikiem $| x |$ .

Jeśli $p e r i o d (x)$ jest własciwym (mniejszym od $| x |$ ) dzielnikiem $x$ , to $x$ nazywamy rozkładalnym, w przeciwnym przypadku $x$ nazywamy słowem pierwotnym (albo nierozkładalnym).

Na przykład $a b a b a b$ jest rozkładalne, natomiast $a b a b a b a$ jest pierwotne.

Lemat Kombinatoryczna własność słów pierwotnych

Jeśli $x$ jest pierwotne to x nie ma wystąpienia wewnątrz xx.

Rysunek 4: Jeśli tekst

x

jest pierwotny, to taka sytuacja jest niemożliwa (

x

nie może występować wewnątrz tekstu

x x

.

Własność ta mówi, że nie może zajść sytuacja przedstawiona na Rysunku 4. Dowód własności korzysta z tzw. lematu o okresowości dla tekstów: jeśli $x$ ma okresy $p, q$ oraz $p + q \leq | x |$ to $n w d (p, q)$ jest również okresem $x$ .

Popatrzmy na rysunek. Gdyby $x$ występował w $x x$ , to $x x$ miałby dwa okresy $p, q$ takie, że $p + q \leq | x x |$ . Z lematu o okresowości wynika wtedy, że $x x$ ma okres mniejszy od $| x |$ i będący dzielnikiem $| x |$ . Zatem słowo $x$ nie byłoby pierwotne, co jest sprzeczne z założeniem. \myskip Jako ćwiczenie pozostawiamy problem sprawdzania w czasie liniowym czy słowo $x$ jest pierwotne.

Analiza złożoności algorytmu BM

Dokładne oszacowanie na liczbę porównań w algorytmie BM wynosi około 3n. Dowód tego faktu jest jednak zbyt skomplikowany. Pokażemy tutaj oszacowanie górne 4n, dolne oszacowanie 3n pozostawiamy jako ćwiczenie.

Jeśli się głębiej zastanowić, to liniowy czas algorytmu BM jest zdumiewający. Algorytm zapomina, jaka część tekstu <mathy</math> pasowała do wzorca $x$ i sprawdza wielokrotnie te same fragmenty, które już poprzednio były sprawdzone z wynikiem pozytywnym. Zjawisko takie nie ma miejsca w algorytmie KMP, gdzie raz sprawdzony pozytywnie symbol w tekście $y$ nie jest już nigdy więcej sprawdzany.

Rysunek 5: Segment

y [i + j - 1 . . i + m]

tekstu

y

jest aktualnym dopasowaniem,

v

oznacza najkrótszy pełny okres sufiksu wzorca

x

,

v

jest również okresem aktualnego dopasowania. Zaciemniony obszar jest częścią tekstu, która nigdy wcześniej nie była odwiedzana (sprawdzana).

Załóżmy, że w danej nieterminalnej iteracji algorytm BM sprawdza segment $y [i + j - 1 . . i + m]$ tekstu $y$ , a następnie wykonuje przesunięcie $s = B M S h i f t [j]$ , gdzie $j > 0$ oraz $s > (m - j) / 3$ . Przez aktualne dopasowanie rozumiemy aktualnie sprawdzany segment tekstu $y$ bez pozycji, na której występuje niezgodność symboli (patrz Rysunek 5).

Niech $k$ będzie najmniejszym pełnym okresem tekstu $x [m - s + 1 . . m]$ , a $v$ niech będzie słowem odpowiadającym temu okresowi. Inaczej mówiąc zakładamy, że mamy taką sytuację jak na Rysunku 5. Zauważmy, że rozważamy tu okresowość w dwóch aspektach: jako liczbę (długość) oraz jako słowo.

Zdefiniujmy własność pierwszego odwiedzenia:

pozycje w segmencie $y [i + j + k . . i + m - 2 . k]$ nie były sprawdzane w poprzednich iteracjach.

Udowodnimy następujący silny i całkowicie nietrywialny fakt.

Lemat

Własność pierwszego odwiedzenia zachodzi w każdej nieterminalnej iteracji algorytmu BM.

Dowód będzie polegał na zauważeniu kilku drobniejszych własności. Następująca własność wynika w sposób oczywisty z założeń: $v$ jest słowem-okresem aktualnego dopasowania oraz $v$ jest sufiksem wzorca.

Wprowadzimy kluczowe pojęcie pozycji krytycznej jako pozycji w aktualnym dopasowaniu $y [i + j + 1 . . i + m]$ , która jest odległa od końca aktualnego dopasowania o wielokrotność $| v |$ oraz od początku co najmniej o $| v |$ .

Mówimy, że poprzednie dopasowane kończyło się na pozycji $q$ w tekście $y$ , jeśli w pewnej poprzedniej iteracji koniec wzorca był przyłożony do pozycji $q$ w $y$ .

Własność 1 Żadne poprzednie dopasowanie nie kończy się na pozycji krytycznej w aktualnym dopasowaniu.

Dowód własności 1 Dowód ma charakter filozoficzny: gdyby własność 1 dla pewnej iteracji nie zachodziła, to nie byłoby tej iteracji. Gdyby poprzednia iteracja kończyła się na pozycji krytycznej, następnym końcem dopasowania byłaby pozycja $i + m + s$ . W ten sposób przeskoczylibyśmy aktualną iterację. Zatem własność 1 zawsze zachodzi.

Własność 2 Wielkość wspólnej częśc aktualnego dopasowania i danego poprzedniego dopasowania jest mniejsza od $k$ . Dowód własności 2. Z własności 1 wynika, że koniec poprzedniego dopasowania nie kończy się na pozycji krytycznej. Gdyby wspólna część była większa niż $k$ , to słowo pierwotne $v$ występowałoby wewnątrz słowa $v v$ , co zaprzecza własności słów pierwotnych. Zatem musi zachodzić własność 2.

Własność 3 Jeśli poprzednie dopasowanie kończy się na pozycji $q$ wewnątrz aktualnego dopasowania i zawiera się całkowicie w aktualnym dopasowaniu, nie ma krytycznej pozycji na prawo od $q$ .

Dowód własności 3. Przypuśćmy, że jest pewna pozycja krytyczna $r$ na prawo od $q$ . Wówczas $r - q$ jest dobrym kandydatem na przesunięcie w Algorytmie BM. Ponieważ algorytm BM wybiera najmniejsze przesunięcie spośród kandydatów na przesunięcie, spełniających warunek 1. i warunek 2., otrzymamy nową pozycję $q 1 < r$ jako koniec następnego dopasowania. Wynika stąd, że mamy sekwencję $q 1 < q 2 < q 3 < .$ . końcowych pozycji poprzednich dopasowań, z których każda jest mniejsza od $r$ . Wszystkie te liczby są różnymi liczbami naturalnymi. W pewnym momencie jedna z nich musi być równa $r$ . W tym momencie mamy poprzednie dopasowanie, kończące się na pozycji krytycznej $r$ . Przeczy to własności 2. Zatem własność 3 musi zachodzić.

Dowód własności pierwszego odwiedzenia. Trzy własności, przed chwilą udowodnione, wystarczają do tego, żeby uzasadnienie własności pierwszego odwiedzenia było proste. Dowód jest przez zaprzeczenie. Przypuśćmy, że w pewnej poprzedniej iteracji odwiedziliśmy "zabroniony" obszar aktualnego dopasowania (zacienioną część tekstu $y$ na Rysunku 5). Niech $q$ będzie końcem tego poprzedniego dopasowania. Zatem $q$ nie jest pozycją krytyczną. Na prawo od niej jest pewna pozycja krytyczna. Jest to sprzeczne z własnością 3. Kończy to dowód własności pierwszego odwiedzenia.

Możemy teraz przystąpić do ostatecznej analizy algorytmu BM.

Theorem 3.1 [Analiza algorytmu BM]

Algorytm BM wykonuje co najwyżej $4 n$ porównań symboli do momentu znalezienia pierwszego wystąpienia wzorca lub zakończenia szukania z wynikiem negatywnym. Algorytm działa w czasie $O (n)$ , współczynnik kosztu nie zależy od rozmiaru alfabetu.

Z własności pierwszego odwiedzenia wynika bezpośrednio: jeśli $s$ jest przesunięciem w nieterminalnej iteracji, to co najwyżej $3 . s$ pozycji tekstu $y$ sprawdzanych w tej iteracji było sprawdzane w poprzednich iteracjach.

Koszt każdej nieterminalnej iteracji można rozdzielić na dwie części.

(1) Koszt odwiedzenia symboli w tekście $y$ po raz pierwszy, (2) Potrojone przesunięcie.

Sumaryczna liczba porównań symboli typu (1) wynosi co najwyżej $n$ , sumaryczna liczba porównań typu (2)wynosi co najwyżej $3 . (n - m)$ , ponieważ suma przesunięć nie przekracza $n - m$ . Dodatkowo może dojść $m$ porównań w terminalej iteracji. Zatem w sumie liczba porównań jest ograniczona przez:

n + 3 (n - m) + m \leq 4 . n

.

Tablica Prefikso-Prefiksów

W fazie preprocessingu algorytmu BM (obliczanie tablicy $B M S h i f t$ ) potrzebny będzie algorym liczenia dodatkowej tablicy $P R E F$ tzw. prefikso-prefiksów. Jest ona modyfikacją tablicy prefikso-sufiksów: $P R E F [i]$ jest długością najdłuższego prefiksu tekstu $x$ , którego wystąpienie rozpoczyna się na pozycji $i$ . Bardziej formalnie:

P R E F [i] = \max {j : x [i . . i + j - 1]

jest prefiksem

x

\}.

Rysunek 6: Typowa sytuacja w algorytmie Prefikso-Prefiksu. Liczymy PREF dla nowej pozycji j, zakładając, że znamy wartości tablicy PREF dla pozycji wcześniejszych.

Przykład

Dla $x = a b a b a b a b a b b$ mamy:

P R E F [1 . . 11] = [11, 0, 8, 0, 6, 0, 4, 0, 2, 0, 0]

.

Jako ćwiczenie pozostawiamy redukcję problemu liczenia tablicy $P R E F$ do liczenia tablicy $P$ (tablica ta była liczona na wykładzie z ASD).

Przedstawimy niezależny interesujący algorytm liczenia tablicy $P R E F$ . W algorytmie liczymy tablicę PREF przeglądając tekst od lewej do prawej. Załóżmy, że przetwarzamy pozycję $j$ -tą (gdzie $j > 1$ ). Zachodzi wtedy następujący niezmiennik (patrz Rysunek 6)

wartości $P R E F [t]$ dla $t < j$ są już policzone

$s < j$ jest pozycją maksymalizującą $s + P R E F [s] - 1$ .

Dodajemy specjalny znacznik końca tekstu na pozycji $m + 1$ w $x$ . Korzystamy z dodatkowej prostej funkcji $Naive - Scan (p, q)$ :

Naive - Scan (p, q)

=

\max {k \geq 1

takie, że

x [p . . p + k - 1] = x [q . . q + k - 1]}

.

Jeśli nie ma takiego $k > 0$ to $Naive - Scan (p, q) = 0$ . Wartość PREF[1] nie jest dla nas interesująca.

Algorytm Prefikso-Prefiksy

$P R E F [1] : = 0$ ; $s : = 1$ ;
for $j : = 2$ to $m$ do
    $k : = j - s + 1$ ; $r : = s + P R E F [s] - 1$ ;
   if $r < j$ then
       $P R E F [j] : = Naive - Scan (j, 1)$ ;
      if $P R E F [j] > 0$ then $s : = j$ ;
   else if $P R E F [k] + k < P R E F [s]$ then
       $P R E F [j] : = P R E F [k]$
   else
       $x : = Naive - Scan (r + 1, r - j + 2)$ ;
       $P R E F [j] : = r - j + 1 + x$ ; $s : = j$ ;

Najważniejszą częścią algorytmu jest przekopiowywanie, w pewnych sytuacjach, wartości $P R E F [k]$ wcześniej policzonych na $P R E F [j]$ . Dzieje się to wtedy, gdy $P r e f [s]$ jest duże i $P R E F [j - s + 1]$ jest małe ( $j - s + 1$ jest wartością $j$ przeskalowaną względem $s$ ).

Obliczanie tablicy BMShift

Pokażemy, że czas konstrukcji tablicy $B M S h i f t$ jest liniowy, podstawową częścią będzie obliczanie tablicy $P R E F$ . Używając algorytmu liczenia $P R E F$ , obliczamy w czasie liniowym symetryczną tablicę $S$ sufisko-sufiksów: $S [j]$ jest długością maksymalnego sufiksu tekstu $x$ , który kończy się na pozycji $j$ . Tablica $S$ odpowiada tablicy $P R E F$ obliczonej dla odwróconego wzorca $x^{R}$ .

Algorytm Sufikso-sufiksy

$x^{R} : =$ odwrócony wzorzec $x$ ;

oblicz tablicę $P R E F$ dla tekstu $x^{R}$ ;

for each { $i$ } do $S [i] : = P R E F [m - i + 1]$ ;

Rysunek 7: Przypadek gdy

B M S h i f t [j] < j

. Dla

j = 22

, oraz przykładowego tekstu rozmiaru

m = 25

, mamy

B M S h i f t [22] = \min {m - k : j = m - S [k] = 22}

. Otrzymujemy

m - S [k] = 22

, zatem

S [k] = 3

. Dla

k = 9, 14, 22

,mamy

S [9] = S [14] = S [22] = 3

, zatem

B M S h i f t [22] = m - 22 = 25 - 22 = 3

.

Obserwacja. Jeśli $B M S h i f t [j] = m - k < j$ , to $S [k] = m - j$ .

Przykład

Dla $j = 22$ i przykładowego wzorca x na Rysunku 7 mamy:

$B M S h i f t [j] = 3$ , oraz $S [25 - 3] = m - j = 3$ .

Gdy korzystamy z powyższej obserwacji, przesunięcia w algorytmie BM obliczane są następująco. Inicjalizujemy $B M S h i f t [j] : = m$ dla każdego $j$ .

Algorytm Oblicz-BMShift

for $k : = 1$ to $n - 1$ do
$j : = m - S [k]$ ; $B M S h i f t [j] : = m - k$

Dla przypadku, gdy $B M S h i f t [j] > j$ po wykonaniu powyższego algorytmu, otrzymane wartości nie muszą być poprawne. W tym przypadku heurystyka niezgodności na jednej pozycji jest ignorowana i sprowadzamy obliczenie do prefikso-sufiksów całego wzorca $x$ . Załóżmy, że $j > 1$ , niech $k$ będzie długością maksymalnego prefiksu wzorca, który jest sufiksem całego wzorca, oraz $k < m - j$ . Przyjmujemy wtedy $B M S h i f t [j] = m - k$ .

Zaawansowane algorytmy i struktury danych/Wykład 1: Różnice pomiędzy wersjami

Aktualna wersja na dzień 22:14, 11 wrz 2023

Spis treści

Algorytm Boyera-Moore'a

Algorytm BM ze słabszą tablicą przesunięć

Pewna własność kombinatoryczna tekstów

Analiza złożoności algorytmu BM

Tablica Prefikso-Prefiksów

Obliczanie tablicy BMShift

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia

@@ Linia 1: / Linia 1: @@
-'''\Large Moduł ZASD:\ zaawansowane algorytmy tekstowe I''' \myskip Tekst jest ciągiem symboli, przyjmujemy żejest on zadany tablicą x[1..k] elementami której są symbole. Liczba <math>k=|x|</math> jest długością (rozmiarem)tekstu.W większości naszych algorytmów jedyne operacje dopuszczalne na symbolach wejściowychto porównania dwóch symboli.
+<font size="6"> Zaawansowane algorytmy tekstowe I </font>
-Postawowym problemem tekstowem jest problem {\em string matchingu} polegający na szukaniu wzorca <math>x=x[1..m]</math> wteście <math>y=y[1..n]</math>. Elementami tablic są symbole. Na kursie z ASD przerabialiśmy algorytm Knutha-Morrisa-Pratt(w skrócie KMP) i jego wariacje. Zaprezentujemy teraz bardziej zaawansowany algorytm dla tego problemu:\algorytm Boyera-Moore'a (w skrócie BM). Pomimo tego, że jest jasne jak ten algorytm działa to jednak jegopełna analiza (złożoność, preprocessing) jest zawansowana.
-Algorytm {\em przykłada} x do tesktu y startując od pozycji i-tej w y, sprawdzamy czy <math>x[1..m]\ =\y[i+1..i+m]</math>.  Pozycja <math>i</math>  {\em wędruje } ze strony lewej do prawej. Jednakże, w przeciwieństwie do algorytmuKMP, równość  <math>x[1..m]\ =\ y[i+1..i+m]</math> sprawdzamy od strony prawej do lewej. Zaczniemy od algorytmu naiwnego.\myskip<!--%------------------------------------------------------------------->\begin{center}\begin{minipage}{14cm}\vskip0.3cm\hspace*{0.6cm}\textbf{Algorytm} \textit{Naiwny-BM};\\\hspace*{1.2cm}<math>i:=0</math>;\\\hspace*{1.2cm}\textbf{while} <math>i<n-m</math> \textbf{do }\\\hspace*{1.8cm}<math>j:=m</math>;\\\hspace*{1.8cm}\textbf{while} <math>j>0</math> \textbf{and} <math>x[j]=y[i+j]</math> \textbf{do}\<math>j:=j-1</math>;\\\hspace*{1.8cm}\textbf{if} <math>j=0</math> \textbf{then return} true;\\\hspace*{1.8cm}\{zachodzi  niezmiennik<math>(i,j)</math>\}\<math>i:=i+1</math>; \vskip 0.1cm \noindent\hspace*{1.2cm}\textbf{return} false;\\\vskip0.4cm\end{minipage}<!--%-->\end{center}<!--%------------------------------------------------------------------->\myskip
-Jeśli zachodzi równość to stwierdzamy, że znaleźliśmy wystąpienie x i kończymy.
+__TOC__
-w przeciwnym razie mamy niezmiennik:
-\begin{center}<math>niezmiennik(i,j): \ x[j+1.. m]=y[i+j+1.. i+m]</math> oraz <math>x[j]\neq y[i+j]</math>.\end{center}
+Algorytmy tekstowe są istotne w wielu dziedzinach informatyki, jak na przykład w edytorach tekstowych lub wyszukiwarkach. Tekst jest naturalnym typem  informacji.
-Korzystając z niezmiennika liczymy większe przesunięcie niż 1. Przesunięcie <math>s</math> jest bezpieczne gdyjesteśmy pewni że w każdej sytuacji pomiędzy <math>i</math> oraz <math>i+s</math> nie zaczyna się żadne wystąpienie wzorca x wtekście y. Przypuśćmy, że x zaczyna od pozycji <math>i+s</math> (zobacz Rysunek&nbsp;[[#figure2-5]], gdzie jestprzedstawionyprzypadek <math>s<j</math>.\\\noindent Zachodzi  wtedy następujący warunek:
-<table>
+Formalnie tekst jest ciągiem symboli. Przyjmujemy, że jest on zadany tablicą <math>x[1..k]</math>, elementami której są symbole. Liczba <math>k=|x|</math> jest długością (rozmiarem) tekstu. W większości naszych algorytmów jedyne operacje dopuszczalne na symbolach wejściowych to porównania dwóch symboli.
+Podstawowym problemem tekstowem jest problem ''string matchingu'', polegający na szukaniu wzorca <math>x=x[1..m]</math> w tekście <math>y=y[1..n]</math>. Elementami tablic są symbole. Na kursie z ASD przerabialiśmy algorytm Knutha-Morrisa-Pratt(w skrócie KMP) i jego wariacje. Zaprezentujemy bardziej zaawansowany algorytm dla tego problemu: algorytm Boyera-Moore'a (w skrócie BM). Pomimo tego, że jest jasne jak ten algorytm działa, to jednak jego pełna analiza (złożoność, preprocessing) jest zawansowana.
+==Algorytm Boyera-Moore'a==
+Algorytm ''przykłada'' <math>x</math> do tekstu <math>y</math> startując od pozycji <math>i</math>-tej w <math>y</math>. Sprawdzamy, czy <math>x[1..m]=y[i+1..i+m]</math>.  Pozycja <math>i</math>  ''wędruje'' ze strony lewej do prawej. Jednakże, w przeciwieństwie do algorytmu KMP, równość  <math>x[1..m]= y[i+1..i+m]</math> sprawdzamy od strony prawej do lewej. Zaczniemy od algorytmu naiwnego.
+{{algorytm|Naiwny-BM|algorytm_naiwny_BM|
+<math>i:=0;</math><br>
+'''while''' <math>i<n-m</math> '''do''<br>
+&nbsp;&nbsp;&nbsp;<math>j:=m</math>,br>
+&nbsp;&nbsp;&nbsp;'''while''' <math>j>0</math> '''and''' <math>x[j]=y[i+j]</math> '''do'''<math>j:=j-1</math><br>
+&nbsp;&nbsp;&nbsp;'''if''' <math>j=0</math> '''then return''' true;<br>
+&nbsp;&nbsp;&nbsp;{zachodzi  niezmiennik<math>(i,j)</math>} <math>i:=i+1</math><br>
+'''return''' false;
+}}
+Jeśli zachodzi równość, to stwierdzamy, że znaleźliśmy wystąpienie <math>x</math> i kończymy.
+W przeciwnym razie mamy niezmiennik:
+<center> <math>niezmiennik(i,j): \ x[j+1.. m]=y[i+j+1.. i+m]</math> oraz <math>x[j]\neq y[i+j]</math>.</center>
+Korzystając z niezmiennika liczymy przesunięcie większe niż 1. Przesunięcie <math>s</math> jest bezpieczne, gdy jesteśmy pewni, że w każdej sytuacji pomiędzy <math>i</math> oraz <math>i+s</math> nie zaczyna się żadne wystąpienie wzorca <math>x</math> w tekście <math>y</math>. Przypuśćmy, że <math>x</math> zaczyna od pozycji <math>i+s</math> (zobacz Rysunek 1, gdzie jest przedstawiony przypadek <math>s<j</math>.)
+Zachodzi wtedy następujący warunek:
+<center><table>
 <tr>
-<td>$warunek1(j,s):$ dla każdego $k$ \  $j<k\leq m\ \Rightarrow\ s>k$ lub $x[k-s]=x[k]$,</td>
+<td>warunek1(j,s): dla każdego k   <math>j<k\leq m\ \Rightarrow\ s>k</math> lub <math>x[k-s]=x[k]</math>,</td>
 </tr>
 <tr>
 <td>
-$warunek2(j,s)$:  $s<j\ \Rightarrow\ x[j-s]\neq x[j]$\ \ \{ własność niezgodności \}.
+warunek2(j,s):  <math>s<j\ \Rightarrow\ x[j-s]\neq x[j]</math> { własność niezgodności }.
 </td>
 </tr>
-</table>
+</table></center>
-<!--%************************************************************-->\begin{figure}%[htb]\begin{center}\includegraphics[width=11.6cm]{teksty_fig10.eps}\caption{Przesuni:ecie w algorytmie BM. Przypadek gdy  <math>s=BMShift[j]<j</math>.}  <span id="figure2-5" \> \end{center}\end{figure}<!--%**********************************************************-->\myskip Definiujemy dwa rodzaje przesunięć, każde z nich dotyczy sufiksu wzorca zaczynającego się od pozycji<math>j<m</math>.
-<table>
-<tr>
+<center>[[Grafika:Zasd_1.jpg]]<br> Rysunek 1: Przesunięcie w algorytmie BM. Przypadek gdy  <math>s=BMShift[j]<j</math>.</center>
-<td>$warunek1(j,s):$ dla każdego $k$ \  $j<k\leq m\ \Rightarrow\ s>k$ lub $x[k-s]=x[k]$,</td>
-</tr>
-<tr>
-<td>
+Definiujemy dwa rodzaje przesunięć. Każde z nich dotyczy sufiksu wzorca zaczynającego się od pozycji<math>j<m</math>.
-$warunek2(j,s)$:  $s<j\ \Rightarrow\ x[j-s]\neq x[j]$\ \ \{ własność niezgodności \}.
-$BMShift'[j]=\min \{ s>0:\ warunek1(j,s)  \},$ </td>
+<math>BMShift'[j]=\min \{ s>0: warunek1(j,s)  \}</math>
-</tr>
-<tr>
+<math>BMShift[j] =\min \{ s>0:warunek1(j,s) \text{ oraz } warunek2(j,s)  \}</math>.
-<td>
-$BMShift[j] =\min \{ s>0:warunek1(j,s) \textrm{ oraz } warunek2(j,s)  \}$.
+Definiujemy również
-</td>
+<center>
-</tr>
+<math>BMShift'[m]=BMShift[m]=m-P[m]=period(x)</math>.</center>
-</table>
-Definiujemy również\begin{center}<math>BMShift'[m]=BMShift[m]=m-P[m]=period(x)</math>.\end{center}Algorytm {BM} jest wersją algorytmu Naiwny-BM, w którym przeunięcie <math>i</math> o jeden zamieniamy na przesunięcie o<math>BMShift[j]</math>, zobacz Rysunek&nbsp;[[#figure2-6]]. \myskip<!--%------------------------------------------------------------------->\begin{center}\begin{minipage}{14cm}\vskip0.3cm\hspace*{0.6cm}\textbf{Algorytm} \textit{BM};\\\hspace*{1.2cm}<math>i:=0</math>;\\\hspace*{1.2cm}\textbf{while} <math>i<n-m</math> \textbf{do }\\\hspace*{1.8cm}<math>j:=m</math>;\\\hspace*{1.8cm}\textbf{while} <math>j>0</math> \textbf{and} <math>x[j]=y[i+j]</math> \textbf{do}\  <math>j:=j-1</math>;\\\hspace*{1.8cm}\textbf{if} <math>j=0</math> \textbf{then return} true;\\\hspace*{1.8cm}\{ <math>niezmiennik(i,j)</math> \} <math>i:=i+BMShift[j]</math>; \vskip 0.1cm \noindent\hspace*{1.2cm}\textbf{return} false;\\\vskip0.4cm\end{minipage}<!--%-->\end{center}<!--%------------------------------------------------------------------->\myskip Udowodnimy potem, że algorytm ten ma złożoność liniową. Jednakże w przeciwieństwie do łatwejanalizy algorytmu KMP w tym przypadku analiza jest skomplikowana. Mamy tu przykład algorytmu, któregopoprawność jest dosyć oczywista, a analiza kosztu jest nietrywialna.
+Algorytm {BM} jest wersją algorytmu Naiwny-BM, w którym przeunięcie <math>i</math> o jeden zamieniamy na przesunięcie o <math>BMShift[j]</math>, zobacz Rysunek 2.
-<!--%************************************************************-->\begin{figure}%[htb]\begin{center}\includegraphics[width=12.3cm]{teksty_fig11.eps}\caption{ Historia algorytmu {BM} na przykładowych tekstach x, y.}  <span id="figure2-6" \> \end{center}\end{figure}<!--%**********************************************************-->Jeśli zastąpimy tablicę <math>BMShift</math> przez <math>BMShift'</math> wówczas czas algorytmu BM staje się kwadratowy. Przykłademtekstów dla których osiągana jest wtedy złożoność kwadratowa są teksty:<center><math>x=ca(ba)^{k} \mbox{ oraz } y=a^{2.k+2}(ba)^{k}.</math></center>Pozostawiamy jako ćwiczenie podanie wzoru na liczbę porównań z tablicą <math>BMShift'</math> dla tych tekstów.<!--%--><!--%************************************************************-->\begin{figure}%[htb]\begin{center}\includegraphics[width=13.3cm]{teksty_fig12.eps}\caption{Działanie dwóch wersji algorytmu BM na przykładowych tekstach. Algorytm BM stosujący przesunięcie<math>BMShift'</math> wykonuje 30 porównań symboli więcej (rysunek z lewej strony) niż normalny algorytm BM stosującytablicę BM (rysunek prawej strony).<!--%BM with <math>D</math>-Shifts makes only 12 comparisons (right).-->}  <span id="figure4.2" \> \end{center}\end{figure}<!--%**********************************************************-->
-Różnica między <math>BMShift</math> i <math>BMShift'</math> wydaje się być podobna do tej między silnymiprefisko-sufiksami i prefikso-sufiksami w algorytmie KMP. W obu przypadkach różnica sprowadza się dowykorzystania jednego bitu informacji, niezgodności dwóch symboli. Podczas gdy nie robi to istotnej różnicy wpesymistycznej złożoności algorytmu KMP, w tym przypadku jest to znacząca różnica między czasemkwadratowym i liniowym.  Porównajmy działanie algorytmu z przesunięciem  <math>BMShift'</math> i of <math>BMShift</math> na tekstach(patrz rysunek)\\\centerline{ <math>x\ =\ cababababa</math>  oraz  <math>y\ =\ aaaaaaaaaababababa</math>.}<!--%--><!--%==================================================================================-->Okresem tekstu <math>x</math> jest każda liczba naturalna niezerowa <math>p</math> taka, że <math>x[i]=x[i+p]</math>, dla każdego i dlaktórego obie strony są zdefiniowane. Przez period(x) oznaczmy minimalny okres x. Okres jest {\em pełny} gdyjest dzielnikiem <math>|x|</math>.
-Jeśli <math>period(x)</math> jest własciwym (mniejszym od <math>|x|</math>) dzielnikeim <math>x</math>  to x nazywamy rozkładalnym, wprzeciwnym przypadku x nazywamy słowem {\em pierwotnym} (albo nierozkładalnym).
+{{algorytm| BM| algorytm_bm|
-Na przykład <math>ababab</math> jest rozkładalne, natomiast <math>abababa</math> jest pierwotne.<!--%-->\myskip %'''Lemat'''\'''(Kombinatoryczna własność słów pierwotnych)'''
+<math>i:=0</math><br>
-Jeśli <math>x</math> jest pierwotne to x nie ma wystąpienia wewnątrz xx.  \myskip<!--%--><!--%************************************************************-->\begin{figure}[bh]\begin{center}\includegraphics[width=6cm]{teksty_fig13.eps}\caption{Jeśli tekst x jest pierwotny to taka sytuacja jest niemozliwa (x nie może wystepowac wewnatrz tekstuxx.) }  <span id="pierwotne" \> \end{center}\end{figure}<!--%**********************************************************-->\myskip Własność ta {\em mówi}, że nie może zajść sytuacja przedstawiona na Rysunku&nbsp;[[#pierwotne]].Dowód własności  korzysta z tzw. {\em lematu o kresowości} dla tekstów: \ jeśli x ma okresy p, q oraz <math>p+q\le |x|</math> to <math>nwd(p,q)</math> jest również okresem x. \myskip Popatrzmy na rysunek, gdyby x wystepowal w xx to xxmiałby dwa okresy p,q, takie, że <math>p+q\le |xx|</math>, z lematu o okresowości wynika wtedy, że xx ma okres mniejszyof <math>|x|</math> i będący dzielnikiem <math>|x|</math>. Zatem słowo x nie byłoby pierwotne, co jest sprzeczne z założeniem.\myskip Jako ćwiczenie pozostawiamy problem sprawdzania w czasie liniowym czy słowo x jest pierwotne.
+'''while''' <math>i<n-m</math> '''do'''<br>
-<!--%------------------ SEKCJA---------------------------------------->
+&nbsp;&nbsp;&nbsp;<math>j:=m</math>;
-Dokładne oszacowanie na liczbę porównań w algorytmie BM wynosi około 3n. Dowód tego faktu jest jednakzbyt skomplikowany. Pokażemy tutaj oszacowanie górne 4n oraz dolne 3n. Zaczniemy od prostszego oszacowaniadolnego. Zastosujmy algorytm BM do tekstów:
+&nbsp;&nbsp;&nbsp;'''while''' <math>j>0</math> '''and''' <math>x[j]=y[i+j]</math> '''do'''<math>j:=j-1</math>;<br>
-<math>y\ =\  (ba^kba^k)^k</math>, gdzie usuwamy ostatni symbol,oraz <math>x\ =\ ba^{k-1}ba^{k-1}</math>.
+&nbsp;&nbsp;&nbsp;'''if''' <math>j=0</math> '''then return''' true;<br>
-\noindentPozostawimay jako ćwiczenie sprawdzenie tego, że dla tych danych liczba porównań symboli wynosi wprzybliżeniu <math>3n</math>, gdzie <math>n=(2k+2)*k-1</math> jest długością <math>y</math>.\myskipPrzejdziemy teraz do górnego oszacowania <math>4n</math>. \myskipJeśli się głębiej zastanowić to liniowy czasalgorytmu BM jest zdumiewający, algorytm zapomina jaka część tekstu y pasowała do wzorca x, i sprawdzawielokrotnie te same fragmenty które już poprzednio były sprawdzone z wynikem pozytywnym. Zjawisko takie niema miejsca w algorytmie KMP, gdzie raz sprawdzony pozytywnie symbol w tekście y nie jest już nigdy więcejsprawdzany.
+&nbsp;&nbsp;&nbsp;{ <math>niezmiennik(i,j)</math> \} <math>i:=i+BMShift[j]</math>; <br>
-<!--%************************************************************-->\begin{figure}%[htb]\begin{center}\includegraphics[width=15cm]{teksty_fig14.eps}\caption{Segment  <math>y[i+j-1.. i+m]</math> tekstu y jest aktualnym dopasowaniem, <math>v</math> oznacza najkrótszy pełny okressufiksu wzorca x, <math>v</math> jest również okresem aktualnego dopasowania. Zaciemniony obszar jest częścią tekstu,która nigdy wcześniej nie była odwiedzana (sprawdzana). }  <span id="figure3-4" \> \end{center}\end{figure}<!--%**********************************************************-->
+'''return''' false;
-Załóżmy, że w danej nieterminalnej iteracji algorytm BM sprawdza segment <math> y[i+j-1.. i+m]</math> tekstu y, anstępnie wykonuje przesunięcie<math>s=BMShift[j]</math>, gdzie <math>j>0</math> oraz<math>s>(m-j)/3</math>.
+}}
-Przez \textit{aktualne dopasowanie} rozumiemy aktualnie sprawdzany segment tekstu y bez pozycji, na którejwystępuje niezgodność symboli, (patrz Rysunek&nbsp;[[#figure3-4]]).
-Niech <math>k</math> będzie najmniejszym pełnym okresem tekstu <math>x[m-s+1.. m]</math>, a  <math>v</math> niech będzie słowemodpowiadającym temu okresowi. Inaczej mówiąc zakładamy, że mamy taką sytuację jak naRysunku&nbsp;[[#figure3-4]]).
+Udowodnimy potem, że algorytm ten ma złożoność liniową. Jednakże w przeciwieństwie do łatwej analizy algorytmu KMP, w tym przypadku analiza jest skomplikowana. Mamy tu przykład algorytmu, którego poprawność jest dosyć oczywista, a analiza kosztu jest nietrywialna.
-Zauważmy, że rozważamy tu okresowość w dwóch aspektach: jako liczbę(długość) oraz jako słowo.
-\noindent Zdefiniujmy '''własność  pierwszego odwiedzenia''':
+<center>[[Grafika:Zasd_2.jpg]]<br> Rysunek 2: Historia algorytmu BM na przykładowych tekstach <math>x, y</math>.</center>
-\begin{quotation}\noindent<math>(*)</math>: \ pozycje  w segmencie <math>y[i+j+k.. i+m-2.k]</math> nie były sprawdzane w poprzednich iteracjach.\end{quotation}\myskipUdowodnimy następujący silny i całkowicie nietrywialny fakt.
-\noindent '''Lemat}.\ Własność {\em pierwszego odwiedzenia''' zachodzi w każdej nieterminalnejiteracji algorytmu BM.
-\noindent Dowód będzie polegał na zauważeniu kilku drobniejszych własności. Następująca  własnośćwynika w sposób oczywisty z założeń: \<!--%\textbf{(Własność podstawowa)\  }--><math>v</math> jest słowem-okresem aktualnego dopasowania oraz  <math>v</math> jestsufiksem wzorca.\myskip<!--%-->Wprowadzimy kluczowe pojęcie {\em pozycji krytycznej} jako pozycji w aktualnym dopasowaniu<math>y[i+j+1..i+m]</math>, która jest odległa od końca aktualnego  dopasowania o wielokrotność <math>|v|</math>,oraz od początku co najmniej o <math>|v|</math>.\myskipMówimy, że poprzednie dopasowane kończyło się na pozycji <math>q</math> w tekście <math>y</math>, jeśli wpewnej poprzedniej iteracji koniec wzorca był przyłożony do pozycji <math>q</math> w <math>y</math>.<!--%-->\paragraph{Własność 1}   żadne poprzednie dopasowanie nie kończy się na pozycji krytycznej w aktualnym dopasowaniu.
+<center>[[Grafika:Zasd_2.jpg]]<br> Rysunek 3: Działanie dwóch wersji algorytmu BM na przykładowych tekstach. Algorytm BM stosujący przesunięcie <math>BMShift'</math> wykonuje 30 porównań symboli więcej (rysunek z lewej strony) niż normalny algorytm BM stosujący tablicę BM (rysunek prawej strony).</center>
-\noindent '''Dowód własności 1}.\ Dowód ma charakter {\em filozoficzny''': gdyby własność 1 dla pewnejiteracji nie zachodziła to by tej iteracji nie było. Gdyby poprzednia iteracja kończyła się na pozycjikrytycznej to następnym końcem dopasowania byłaby pozycja <math>i+m+s</math>.  W ten sposób byśmy przeskoczyliaktualną iterację. Zatem własność 1 zawsze zachodzi.<!--%-->\paragraph{Własność 2}  Wielkość wspólnej częśc aktualnego dopasowania idanego poprzedniego dopasowania jest mniejsza od <math>k</math>. \myskip '''Dowód własności 2'''.\ Z własności 1wynika, że koniec poprzedniego dopasowania nie kończy się na pozycji krytycznej. Gdyby wspólna część byławiększa niż <math>k</math> to słowo pierwotne <math>v</math> występowałoby wewnątrz słowa <math>vv</math>, co zaprzecza własności słówpierwotnych. Zatem musi zachodzić własność 2.<!--%-->\noindent \paragraph{Własność 3.}\ Jeśli poprzednie dopasowanie kończy się na pozycji <math>q</math> wewnątrzaktualnego dopasowania i zawiera się całkowicie w aktualnym dopasowaniu. Wtedy nie ma krytycznej pozycji naprawo od&nbsp;<math>q</math>.\myskip'''Dowód własności 3.'''\ Przypuśćmy, że jest pewna pozycja krytyczna <math>r</math> na prawo od <math>q</math>. Wówczas<math>r-q</math> jest dobrym kandydatem na przesunięcie w Algorytmie {BM}. Ponieważ algorytm BM wybiera najmniejszeprzesunięcie spośród kandydatów na przesunięcie spełniających warunek1 i warunek2 otrzymamy nową pozycję<math>q1<r</math> jako koniec następnego dopasowania. Wynika stąd, że mamy sekwencję <math>q1<q2<q3<..</math>, końcowych pozycjipoprzednich dopasowań z których każda jest mniejsza od <math>r</math>. Wszystkie te liczby są różnymi liczbaminaturalnymi, w pewnym momencie jedna z nich musi być równa <math>r</math>. W tym momencie mamy poprzednie dopasowaniekończące się na pozycji krytycznej <math>r</math>. Przeczy to własności 2. Zatem własnośc 3 musi zachodzić.<!--%-->\paragraph'''Dowód własności pierwszego odwiedzenia.'''\Trzy własności przed chwilą udowdnione wystarczją do tego, żeby uzasadnienie własności pierwszego odwiedzeniabyło proste. Dowód jest przez zaprzeczenie. Przypuśćmy, że w pewnej poprzedniejiteracji odwiedziliśmy {\em zabroniony} obszar aktualnego dopasowania (zacienioną częśćtekstu y na Rysunku&nbsp;[[#figure3-4]]).  Niech<math>q</math> będzie końcem tego poprzedniego dopasowania. Zatem  <math>q</math> nie jest pozycją krytyczną, na prawo od niej jestpewna pozycja krytyczna. Jest to sprzeczne z własnością 3.Kończy to dowód własności pierwszego odwiedzenia.\myskipMożemy teraz przystąpić do ostatecznej analizy algorytmu BM.
-\begin{theorem} <span id="Theorem 3.1}{\rm [Analiza algorytmu BM]" \> \\Algorytm BM wykonuje co najwyżej <math>4n</math> porównań symboli do momentu znalezieniapierwszego wystąpienia wzorca lub zakończenia szukania z wynikiem negatywnym.Algorytm działa w czasie <math>O(n)</math>, współczynnik kosztu nie zależy od rozmiarualfabetu.\end{theorem}
+== Algorytm BM ze słabszą tablicą przesunięć ==
-\noindentZ własności {\em pierwszego odwiedzenia} wynika bezpośrednio:
+Jeśli zastąpimy tablicę <math>BMShift</math> przez <math>BMShift'</math>, wówczas czas algorytmu BM staje się kwadratowy. Przykładem tekstów, dla których osiągana jest wtedy złożoność kwadratowa są:
-jeśli  <math>s</math> jest przesunięciem w nieterminalnej iteracji, to co najwyżej <math>3.s</math> pozycji tekstu y sprawdzanych wtej iteracji było sprawdzane w poprzednich iteracjach. \myskip Koszt każdej nieterminalnej iteracji możnarozdzielić na dwie części.
+<center><math>x=ca(ba)^{k} \mbox{ oraz } y=a^{2.k+2}(ba)^{k}</math>.</center>
-#Koszt odwiedzenia symboli w tekście <math>y</math> po raz pierwszy,
-#Potrojone przesunięcie.
+Pozostawiamy jako ćwiczenie podanie wzoru na liczbę porównań z tablicą <math>BMShift'</math> dla tych tekstów.
-Sumaryczna liczba porównań symboli typu (1) wynosi co najwyżej <math>n</math>, sumaryczna liczba porównań typu (2)wynosi co najwyżej<math>3.(n-m)</math>, ponieważ suma przesunięć nie przekracza <math>n-m</math>. Dodatkowo może dojść <math>m</math> porównań w terminalejiteracji. Zatem w sumie liczba porównań jest ograniczona przez:<center><math>n+3(n-m)+m\leq 4.n.</math></center>
-<!--%=====================================================================================================--><!--%-->\subsection*{Tablica Prefisko-Prefiksów}<!--%\myskip-->W fazie {\em preprocessing}u algorytmu BM (obliczanie tablicy <math>BMShift</math>) potrzebny będzie algorym liczeniatablicy prefikso-prefiksów.  Modyfikacją tablicy prefikso-sufiksów jest tablica prefikso-prefiksów: <math>PREF[i]</math>jest długośćią najdłuższego prefiksu tekstu x, którego wystąpienie rozpoczyna się na pozycji <math>i</math>.Bardziej formalnie:
-\begin{center}<math>PREF[i]=\max \{ j:\ x[i.. i+j-1]</math> jest prefiksem <math>x</math> \}.\end{center}\myskip '''Przykład.'''\  Dla <math>x\ =\ abababababb</math> mamy:<center><math>PREF[1..11]\ =\ [11,\ 0,\ 8,\ 0,\ 6,\ 0,\ 4,\ 0,\ 2,\ 0,\ 0].</math></center>
+Różnica między <math>BMShift</math> i <math>BMShift'</math> wydaje się być podobna do tej między silnymi prefikso-sufiksami i prefikso-sufiksami w algorytmie KMP. W obu przypadkach różnica sprowadza się do wykorzystania jednego bitu informacji, niezgodności dwóch symboli. Podczas gdy nie robi to istotnej różnicy w pesymistycznej złożoności algorytmu KMP, w tym przypadku jest to znacząca różnica między czasem kwadratowym i liniowym.  Porównajmy działanie algorytmu z przesunięciem  <math>BMShift'</math> i of <math>BMShift</math> na tekstach(patrz rysunek)
-Jako ćwiczenie pozostawiamy redukcję problemu liczenia tablicy <math>PREF</math> do liczenia tablicy <math>P</math>, co jużpotrafimy. przeskalowanym <math>j</math> względem s) jest małe, patrz rysunek.<!--%**********************************************************--><!--%--------+---------+---------+---------+---------+---------+------->
-Przedstawimy niezależny interesujący algorytm liczenia tablicy <math>PREF</math>. W algorytmie liczymy tablicę PREFprzeglądając tekst od lewej do prawej. Załóżmy, że przetwarzamy pozycję   <math>j</math>-tą (gdzie <math>j>1</math>), wtedyzachodzi następujący niezmiennik (patrz Rysunek&nbsp;[[#pref]]):\begin{quotation}\noindentwartości <math>PREF[t]</math> dla <math>t <j</math> są już policzone\\<math>s<j</math> jest pozycją maksymalizującą  <math>s + PREF[s] - 1</math>.\end{quotation}\noindent Dodajemy specjalny znacznik końca tekstu na pozycji  <math>m+1</math> w <math>x</math>.Korzystamy z dodatkowej prostej funkcji <math>\textit{Naive-Scan}(p,q)</math>:
+<center><math>x= cababababa</math>  oraz  <math>y= aaaaaaaaaababababa</math>.</center>
-\begin{center}<math>\textit{Naive-Scan}(p,q)</math> = <math>\max\{k \ge 1</math> takie, że <math>x[p .. p+k-1] = x[q .. q+k-1]\}</math>.\end{center}Jeśli nie ma takiego  <math>k>0</math> to <math>\textit{Naive-Scan}(p,q)=0</math>. Wartość PREF[1] nie jest dla nas interesująca.
-\begin{figure}%[hb]\begin{center}\includegraphics[width=15.5cm]{teksty_fig2.eps}\caption{Typowa sytuacja w algorytmie Prefikso-Prefiksy. Liczymy PREF dla nowej pozycji <math>j</math>, zakladając, żeznamy wartości tablicy PREF dla pozycji wczesniejszych. }  <span id="pref" \> \end{center}\end{figure}\myskip<!--%------------------------------------------------------------------->\begin{center}\begin{minipage}{12cm}\vskip0.3cm \hspace*{0.6cm}\textbf{Algorytm} <math>\textit{Prefikso-Prefiksy}</math>;\vskip 0.1cm \noindent<!--%-->\hspace*{1.2cm}<math>PREF[1]:=0</math>;  <math>s:=1</math>;\vskip 0.1cm \noindent \hspace*{1.2cm}\textbf{for} <math>j:=2</math> \textbf{to} <math>m</math>\textbf{do}\vskip 0.1cm \noindent \hspace*{1.8cm}<math>k:=j-s+1</math>;\ <math>r:=s+PREF[s]-1</math>;\vskip 0.1cm \noindent\hspace*{1.8cm}\textbf{if} <math>r<j</math> \textbf{then }\\<!--%\hspace*{1.8cm}\textbf{begin}\\-->\hspace*{2.4cm}<math>PREF[j]:=\textit{Naive-Scan}(j,1)</math>;\\\hspace*{2.4cm}  \textbf{if} <math>PREF[j]>0</math> \textbf{then} <math>s</math> :=<math>j</math>; \\<!--%\hspace*{1.8cm} \textbf{end}\\-->\hspace*{1.8cm}\textbf{else if} <math>PREF[k]+k<PREF[s]</math> \textbf{then}\\\hspace*{2.4cm}<math>PREF[j]:=PREF[k]</math>\\\hspace*{1.8cm}\textbf{else}\\\hspace*{2.4cm}<math>x:=\textit{Naive-Scan}(r+1,r-j+2)</math>;\\\hspace*{2.4cm}<math>PREF[j]:=r-j+1+x</math>;\  <math>s:=j</math>;\\\vskip0.4cm\end{minipage}\end{center}\myskip<!--%***********************************************************-->Najważniejszą częścią algorytmu jest przekopiowywanie, w pewnych sytuacjach, wartości <math>PREF[k]</math> wcześniejpoliczonych na <math>PREF[j]</math>. Dzieje się to wtedy, gdy <math>Pref[s]</math> jest duże i <math>PREF[j-s+1]</math> jest małe (<math>j-s+1</math> jestwartością <math>j</math> przeskalowaną względem <math>s</math>).<!--%------------------------------------------------------------------->
+== Pewna własność kombinatoryczna tekstów ==
-Pokażemy że czas konstrukcji tablcy <math>BMShift</math> jest liniowy, podstawową częścią  będzieobliczanie tablicy <math>PREF</math>. Używając algorytmu liczenia <math>PREF</math> obliczamy w czasie liniowym symetryczną tablicę<math>S</math> sufisko-sufiksów: <math>S[j]</math> jest długością maksymalnego sufiksu tekstu <math>x</math> który kończy się na pozycji<math>j</math>. Tablica <math>S</math> odpowiada tablicy <math>PREF</math> obliczonej dla odwróconego wzorca <math>x^R</math>.
-<!--%------------------------------------------------------------------->\begin{center}\begin{minipage}{10cm}\vskip0.3cm\hspace*{0.6cm}\textbf{Algorytm} Sufikso-sufiksy;\\\hspace*{1.2cm}<math>x^R</math>:=odwrócony wzorzec <math>x</math>;\\\hspace*{1.2cm}oblicz tablicę <math>PREF</math> dla tekstu <math>x^R</math>;\\\hspace*{1.2cm}\textbf{for each {<math>i</math>} do}\  \ <math>S[i]:= PREF[m-i+1]</math>;\\\vskip0.4cm\end{minipage}\end{center}<!--%------------------------------------------------------------------->\myskip<!--%***********************************************************-->\begin{figure}%[htb]\begin{center}\includegraphics[width=15cm]{teksty_fig9.eps}\caption{Przypadek gdy <math>BMShift[j] < j</math>. Dla  <math>j=22</math>, oraz przykładowgo tekstu rozmiaru <math>m=25</math>, mamy<math>BMShift[22]\ =\ \min\{m-k\ :\ j=m-S[k]=22\}</math>. Otrzymujemy <math>m-S[k]=22</math>, zatem  <math>S[k]=3</math>. Dla  <math>k=9,\ 14,\ 22</math>,mamy <math>S[9]=S[14]=S[22]=3</math>, zatem  <math>BMShift[22] = m-22 = 25-22 = 3</math>. }  <span id="BM-shifts" \> \end{center}\end{figure}<!--%**********************************************************-->
+Okresem tekstu <math>x</math> jest każda niezerowa  liczba naturalna  <math>p</math> taka, że <math>x[i]=x[i+p]</math> dla każdego <math>i</math>, dla którego obie strony są zdefiniowane. Przez <math>period(x)</math> oznaczmy minimalny okres <math>x</math>. Okres jest \mathit{ pełny} gdy jest dzielnikiem <math>|x|</math>.
-\myskip '''Obserwacja.'''\ Jeśli <math>BMShift[j] = m-k < j</math>, to <math>S[k]=m-j</math>. \myskip''' Przykład.'''\  Dla <math>j=22</math> iprzykładowego wzorca x na Rysunku&nbsp;[[#BM-shifts]] mamy:
-<math>BMShift[j]=3</math>, oraz <math>S[25-3]=m-j=3</math>. \myskip Korzystając z powyższej  obserwacji przesunięcia w algorytmie BMobliczane są następująco. Inicjalizujemy <math>BMShift[j] := m</math> dla każdego <math>j</math>. \myskip<!--%------------------------------------------------------------------->\begin{center}\begin{minipage}{8cm}\vskip0.3cm\hspace*{0.6cm}\textbf{Algorytm} Oblicz-BMShift;\\\hspace*{1.2cm}\textbf{for} <math>k:=1</math>  \textbf{to} <math>n-1</math> \textbf{do }\\\hspace*{1.8cm}<math>j := m-S[k]</math>;  <math>BMShift[j] := m-k</math>;\\<!--%\hspace*{1.2cm}\textbf{end}\\-->\vskip0.4cm\end{minipage}\end{center}<!--%------------------------------------------------------------------->\myskipDla przypadku, gdy <math>BMShift[j] > j</math> po wykonaniu powyższego algorytmu,otrzymane wartości nie muszą być poprawne. W tym przypadku heurystykaniezgodności na jednej pozycji jest ignorowana i sprowadzamy obliczenie do prefikso-sufiksów całego wzorca<math>x</math>. Załóżmy wtedy, że <math>j>1</math>, niech <math>k</math> będzie długości"maksymalnego prefiksu wzorca, który jest sufiksemcałego wzorca, oraz <math>k<m-j</math>, wtedy przyjmujemy <math>BMShift[j]= m-k.</math><!--%--------+---------+---------+---------+---------+---------+---------+---------+-->
+Jeśli <math>period(x)</math> jest własciwym (mniejszym od <math>|x|</math>) dzielnikiem  <math>x</math>,  to <math>x</math> nazywamy rozkładalnym, w przeciwnym przypadku <math>x</math> nazywamy słowem ''pierwotnym'' (albo nierozkładalnym).
+Na przykład <math>ababab</math> jest rozkładalne, natomiast <math>abababa</math> jest pierwotne.
+{{lemat|Kombinatoryczna własność słów pierwotnych|lemat_komb_wlasn_slow_pierw|
+Jeśli <math>x</math> jest pierwotne to x nie ma wystąpienia wewnątrz xx.
+}}
+<center> [[Grafika:Zasd_4.jpg]]<br> Rysunek 4: Jeśli tekst <math>x</math> jest pierwotny, to taka sytuacja jest niemożliwa (<math>x</math> nie może występować wewnątrz tekstu <math>xx</math>.</center>
+Własność ta mówi, że nie może zajść sytuacja przedstawiona na Rysunku 4. Dowód własności korzysta z tzw. ''lematu o okresowości'' dla tekstów:  jeśli <math>x</math> ma okresy <math>p, q</math> oraz <math>p+q\le |x|</math> to <math>nwd(p,q)</math> jest również okresem <math>x</math>.
+Popatrzmy na rysunek. Gdyby <math>x</math> występował w <math>xx</math>, to <math>xx</math> miałby dwa okresy <math>p,q</math> takie, że <math>p+q\le |xx|</math>. Z lematu o okresowości wynika wtedy, że <math>xx</math> ma okres mniejszy od <math>|x|</math> i będący dzielnikiem <math>|x|</math>. Zatem słowo <math>x</math> nie byłoby pierwotne, co jest sprzeczne z założeniem. \myskip Jako ćwiczenie pozostawiamy problem sprawdzania w czasie liniowym czy słowo <math>x</math> jest pierwotne.
+== Analiza złożoności algorytmu BM ==
+Dokładne oszacowanie na liczbę porównań w algorytmie BM wynosi około 3n. Dowód tego faktu jest jednak zbyt skomplikowany. Pokażemy tutaj oszacowanie górne 4n, dolne oszacowanie 3n pozostawiamy jako ćwiczenie.
+Jeśli się głębiej zastanowić, to liniowy czas algorytmu BM jest zdumiewający. Algorytm zapomina, jaka część tekstu <mathy</math> pasowała do wzorca <math>x</math> i sprawdza wielokrotnie te same fragmenty, które już poprzednio były sprawdzone z wynikiem pozytywnym. Zjawisko takie nie ma miejsca w algorytmie KMP, gdzie raz sprawdzony pozytywnie symbol w tekście <math>y</math> nie jest już nigdy więcej sprawdzany.
+<center>[[Grafika:Zasd_5.jpg]]<br> Rysunek 5: Segment  <math>y[i+j-1.. i+m]</math> tekstu <math>y</math> jest aktualnym dopasowaniem, <math>v</math> oznacza najkrótszy pełny okres sufiksu wzorca <math>x</math>, <math>v</math> jest również okresem aktualnego dopasowania. Zaciemniony obszar jest częścią tekstu, która nigdy wcześniej nie była odwiedzana (sprawdzana).</center>
+Załóżmy, że w danej nieterminalnej iteracji algorytm BM sprawdza segment <math>y[i+j-1.. i+m]</math> tekstu <math>y</math>, a następnie wykonuje przesunięcie <math>s=BMShift[j]</math>, gdzie <math>j>0</math> oraz<math>s>(m-j)/3</math>.
+Przez ''aktualne dopasowanie'' rozumiemy aktualnie sprawdzany segment tekstu <math>y</math> bez pozycji, na której występuje niezgodność symboli (patrz Rysunek 5).
+Niech <math>k</math> będzie najmniejszym pełnym okresem tekstu <math>x[m-s+1.. m]</math>, a  <math>v</math> niech będzie słowem odpowiadającym temu okresowi. Inaczej mówiąc zakładamy, że mamy taką sytuację jak na Rysunku 5.
+Zauważmy, że rozważamy tu okresowość w dwóch aspektach: jako liczbę (długość) oraz jako słowo.
+Zdefiniujmy '''własność  pierwszego odwiedzenia''':
+* pozycje  w segmencie <math>y[i+j+k.. i+m-2.k]</math> nie były sprawdzane w poprzednich iteracjach.
+Udowodnimy następujący silny i całkowicie nietrywialny fakt.
+{{lemat|||
+Własność ''pierwszego odwiedzenia'' zachodzi w każdej nieterminalnej iteracji algorytmu BM.
+}}
+Dowód będzie polegał na zauważeniu kilku drobniejszych własności. Następująca własność wynika w sposób oczywisty z założeń: <math>v</math> jest słowem-okresem aktualnego dopasowania oraz  <math>v</math> jest sufiksem wzorca.
+Wprowadzimy kluczowe pojęcie ''pozycji krytycznej'' jako pozycji w aktualnym dopasowaniu <math>y[i+j+1..i+m]</math>, która jest odległa od końca aktualnego dopasowania o wielokrotność <math>|v|</math> oraz od początku co najmniej o <math>|v|</math>.
+Mówimy, że poprzednie dopasowane kończyło się na pozycji <math>q</math> w tekście <math>y</math>, jeśli w pewnej poprzedniej iteracji koniec wzorca był przyłożony do pozycji <math>q</math> w <math>y</math>.
+'''Własność 1''' Żadne poprzednie dopasowanie nie kończy się na pozycji krytycznej w aktualnym dopasowaniu.
+'''Dowód własności 1''' Dowód ma charakter ''filozoficzny'': gdyby własność 1  dla pewnej iteracji nie zachodziła, to nie byłoby tej iteracji. Gdyby poprzednia iteracja kończyła się na pozycji krytycznej, następnym końcem dopasowania byłaby pozycja <math>i+m+s</math>.  W ten sposób przeskoczylibyśmy aktualną iterację. Zatem własność 1 zawsze zachodzi.
+'''Własność 2'''  Wielkość wspólnej częśc aktualnego dopasowania i danego poprzedniego dopasowania jest mniejsza od <math>k</math>.
+'''Dowód własności 2'''. Z własności 1 wynika, że koniec poprzedniego dopasowania nie kończy się na pozycji krytycznej. Gdyby wspólna część była większa niż <math>k</math>, to słowo pierwotne <math>v</math> występowałoby wewnątrz słowa <math>vv</math>, co zaprzecza własności słów pierwotnych. Zatem musi zachodzić własność 2.
+'''Własność 3''' Jeśli poprzednie dopasowanie kończy się na pozycji <math>q</math> wewnątrz aktualnego dopasowania i zawiera się całkowicie w aktualnym dopasowaniu, nie ma krytycznej pozycji na prawo od&nbsp;<math>q</math>.
+'''Dowód własności 3.''' Przypuśćmy, że jest pewna pozycja krytyczna <math>r</math> na prawo od <math>q</math>. Wówczas <math>r-q</math> jest dobrym kandydatem na przesunięcie w Algorytmie BM. Ponieważ algorytm BM wybiera najmniejsze przesunięcie spośród kandydatów na przesunięcie, spełniających warunek 1. i warunek 2., otrzymamy nową pozycję <math>q1<r</math> jako koniec następnego dopasowania. Wynika stąd, że mamy sekwencję <math>q1<q2<q3<.</math>. końcowych pozycji poprzednich dopasowań, z których każda jest mniejsza od <math>r</math>. Wszystkie te liczby są różnymi liczbami naturalnymi. W pewnym momencie jedna z nich musi być równa <math>r</math>. W tym momencie mamy poprzednie dopasowanie, kończące się na pozycji krytycznej <math>r</math>. Przeczy to własności 2. Zatem własność 3 musi zachodzić.
+'''Dowód własności pierwszego odwiedzenia.''' Trzy własności, przed chwilą udowodnione, wystarczają do tego, żeby uzasadnienie własności pierwszego odwiedzenia było proste. Dowód jest przez zaprzeczenie. Przypuśćmy, że w pewnej poprzedniej iteracji odwiedziliśmy "zabroniony" obszar aktualnego dopasowania (zacienioną część tekstu <math>y</math> na Rysunku 5).  Niech<math>q</math> będzie końcem tego poprzedniego dopasowania. Zatem  <math>q</math> nie jest pozycją krytyczną. Na prawo od niej jest pewna pozycja krytyczna. Jest to sprzeczne z własnością 3. Kończy to dowód własności pierwszego odwiedzenia.
+Możemy teraz przystąpić do ostatecznej analizy algorytmu BM.
+'''Theorem 3.1''' [Analiza algorytmu BM]
+Algorytm BM wykonuje co najwyżej <math>4n</math> porównań symboli do momentu znalezienia pierwszego wystąpienia wzorca lub zakończenia szukania z wynikiem negatywnym. Algorytm działa w czasie <math>O(n)</math>, współczynnik kosztu nie zależy od rozmiaru alfabetu.
+Z własności ''pierwszego odwiedzenia'' wynika bezpośrednio:
+jeśli  <math>s</math> jest przesunięciem w nieterminalnej iteracji, to co najwyżej <math>3.s</math> pozycji tekstu <math>y</math> sprawdzanych w tej iteracji było sprawdzane w poprzednich iteracjach.
+Koszt każdej nieterminalnej iteracji można rozdzielić na dwie części.
+(1) Koszt odwiedzenia symboli w tekście <math>y</math> po raz pierwszy,
+(2) Potrojone przesunięcie.
+Sumaryczna liczba porównań symboli typu (1) wynosi co najwyżej <math>n</math>, sumaryczna liczba porównań typu (2)wynosi co najwyżej<math>3.(n-m)</math>, ponieważ suma przesunięć nie przekracza <math>n-m</math>. Dodatkowo może dojść <math>m</math> porównań w terminalej iteracji. Zatem w sumie liczba porównań jest ograniczona przez:
+<center><math>n+3(n-m)+m\leq 4.n</math>.</center>
+=== Tablica Prefikso-Prefiksów===
+W fazie ''preprocessing''u algorytmu BM (obliczanie tablicy <math>BMShift</math>) potrzebny będzie algorym liczenia dodatkowej  tablicy <math>PREF</math>  tzw. prefikso-prefiksów.  Jest ona modyfikacją tablicy prefikso-sufiksów: <math>PREF[i]</math> jest długością najdłuższego prefiksu tekstu <math>x</math>, którego wystąpienie rozpoczyna się na pozycji <math>i</math>. Bardziej formalnie:
+<center><math>PREF[i]=\max \{ j:\ x[i.. i+j-1]</math> jest prefiksem <math>x</math> \}.</center>
+<center> [[Grafika:Zasd_6.jpg]]<br>Rysunek 6: Typowa sytuacja w algorytmie Prefikso-Prefiksu. Liczymy PREF dla nowej pozycji j, zakładając, że znamy wartości tablicy PREF dla pozycji wcześniejszych.</center>
+{{przyklad|||
+Dla <math>x= abababababb</math> mamy:
+<center><math>PREF[1..11]= [11,\ 0,\ 8,\ 0,\ 6,\ 0,\ 4,\ 0,\ 2,\ 0,\ 0]</math>.</center>
+}}
+Jako ćwiczenie pozostawiamy redukcję problemu liczenia tablicy <math>PREF</math> do liczenia tablicy <math>P</math> (tablica ta była liczona na wykładzie z ASD).
+Przedstawimy niezależny interesujący algorytm liczenia tablicy <math>PREF</math>. W algorytmie liczymy tablicę PREF przeglądając tekst od lewej do prawej. Załóżmy, że przetwarzamy pozycję   <math>j</math>-tą (gdzie <math>j>1</math>). Zachodzi wtedy następujący niezmiennik (patrz Rysunek 6)
+wartości <math>PREF[t]</math> dla <math>t <j</math> są już policzone
+<math>s<j</math> jest pozycją maksymalizującą  <math>s + PREF[s] - 1</math>.
+Dodajemy specjalny znacznik końca tekstu na pozycji <math>m+1</math> w <math>x</math>. Korzystamy z dodatkowej prostej funkcji <math>\textit{Naive-Scan}(p,q)</math>:
+<center><math>\textit{Naive-Scan}(p,q)</math> = <math>\max\{k \ge 1</math> takie, że <math>x[p .. p+k-1] = x[q .. q+k-1]\}</math>.</center>
+Jeśli nie ma takiego <math>k>0</math> to <math>\textit{Naive-Scan}(p,q)=0</math>. Wartość PREF[1] nie jest dla nas interesująca.
+{{algorytm| Prefikso-Prefiksy|algorytm_prefikso_prefiksy|
+<math>PREF[1]:=0</math>;  <math>s:=1</math>;<br>
+'''for''' <math>j:=2</math> '''to''' <math>m</math>'''do'''<br>
+&nbsp;&nbsp;&nbsp;<math>k:=j-s+1</math>; <math>r:=s+PREF[s]-1</math>;<br>
+&nbsp;&nbsp;&nbsp;'''if''' <math>r<j</math> '''then'''<br>
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>PREF[j]:=\textit{Naive-Scan}(j,1)</math>;<br>
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''if''' <math>PREF[j]>0</math> '''then''' <math>s :=j</math>; <br>
+&nbsp;&nbsp;&nbsp;'''else if''' <math>PREF[k]+k<PREF[s]</math> '''then''' <br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>PREF[j]:=PREF[k]</math><br>
+&nbsp;&nbsp;&nbsp;'''else''' <br>
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>x:=\textit{Naive-Scan}(r+1,r-j+2)</math>;<br>
+&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>PREF[j]:=r-j+1+x</math>;<math>s:=j</math>;
+}}
+Najważniejszą częścią algorytmu jest przekopiowywanie, w pewnych sytuacjach, wartości <math>PREF[k]</math> wcześniej policzonych na <math>PREF[j]</math>. Dzieje się to wtedy, gdy <math>Pref[s]</math> jest duże i <math>PREF[j-s+1]</math> jest małe (<math>j-s+1</math> jest wartością <math>j</math> przeskalowaną względem <math>s</math>).
+==Obliczanie tablicy BMShift==
+Pokażemy, że czas konstrukcji tablicy <math>BMShift</math> jest liniowy, podstawową częścią  będzie obliczanie tablicy <math>PREF</math>. Używając algorytmu liczenia <math>PREF</math>, obliczamy w czasie liniowym symetryczną tablicę <math>S</math> sufisko-sufiksów: <math>S[j]</math> jest długością maksymalnego sufiksu tekstu <math>x</math>, który kończy się na pozycji<math>j</math>. Tablica <math>S</math> odpowiada tablicy <math>PREF</math> obliczonej dla odwróconego wzorca <math>x^R</math>.
+{{algorytm|Sufikso-sufiksy|algorytm_sufikso_sufiksy|
+<math>x^R:=</math> odwrócony wzorzec <math>x</math>;
+oblicz tablicę <math>PREF</math> dla tekstu <math>x^R</math>;
+'''for each''' {<math>i</math>} '''do''' <math>S[i]:= PREF[m-i+1]</math>;
+}}
+<center>[[Grafika:Zasd_7.jpg]]<br> Rysunek 7: Przypadek gdy <math>BMShift[j] < j</math>. Dla  <math>j=22</math>, oraz przykładowego tekstu rozmiaru <math>m=25</math>, mamy <math>BMShift[22]= \min\{m-k\ :\ j=m-S[k]=22\}</math>. Otrzymujemy <math>m-S[k]=22</math>, zatem  <math>S[k]=3</math>. Dla  <math>k=9,\ 14,\ 22</math>,mamy <math>S[9]=S[14]=S[22]=3</math>, zatem  <math>BMShift[22] = m-22 = 25-22 = 3</math>. </center>
+'''Obserwacja.''' Jeśli <math>BMShift[j] = m-k < j</math>, to <math>S[k]=m-j</math>.
+{{przyklad|||
+Dla <math>j=22</math> i przykładowego wzorca x na Rysunku 7 mamy:
+<math>BMShift[j]=3</math>, oraz <math>S[25-3]=m-j=3</math>.
+}}
+Gdy korzystamy z powyższej obserwacji, przesunięcia w algorytmie BM obliczane są następująco.
+Inicjalizujemy <math>BMShift[j] := m</math> dla każdego <math>j</math>.
+{{algorytm|Oblicz-BMShift|algorytm_oblicz_BMShift|
+'''for''' <math>k:=1</math>  '''to''' <math>n-1</math> '''do''' <br>
+&nbsp;&nbsp;&nbsp;<math>j := m-S[k]</math>;  <math>BMShift[j] := m-k</math>
+}}
+Dla przypadku, gdy <math>BMShift[j] > j</math> po wykonaniu powyższego algorytmu, otrzymane wartości nie muszą być poprawne. W tym przypadku heurystyka niezgodności na jednej pozycji jest ignorowana i sprowadzamy obliczenie do prefikso-sufiksów całego wzorca <math>x</math>. Załóżmy, że <math>j>1</math>, niech <math>k</math> będzie długością maksymalnego prefiksu wzorca, który jest sufiksem całego wzorca, oraz <math>k<m-j</math>. Przyjmujemy wtedy <math>BMShift[j]= m-k</math>.