Boyer-Moore_Beispiel.txt

Boyer-Moore

Pattern gtccgtc
Template atgggtccgtccgtcagtccgtctg


1. Bad Character
Postition des am weitesten rechts liegenden Vorkommens
S. 18

a = 0
c = 7
g = 5
t = 6

2. Good Suffix rule
S. 29
a) Z-Boxen auf Pr

ctgcctg
Z(i) 001300

b) N(j) - Werte
S. 30
1234567
gtccgtc
N(j) 0031000

c) L(i) - Werte
S. 33
for j:=1 to n-1
i:= n-N(j)+1
if (i<=n) then !!!!AENDERUNG!!!!
L(i):=j

12345678
gtccgtc
L(i) 00003046

2. Suche von Pattern in Template
S. 34

i BC = i-BC[char(i)] GS=n-L[i+1]
atgggtccgtccgtcagtccgtctg
|
gtccgtc 4 4 - 5 = -1 7 - 3 = 4
gtccgtc 0 Gefunden = 5, erhöhe um 1
|
gtccgtc 6 6 - 7 = -1 7 - 4 = 3
gtccgtc Gefunden = 9, erhöhe k um 1
|
gtccgtc 7 7 - 0 = 7 7 - 6 = 1
gtccgtc Gefunden = 17, erhöhe k um 1
|
gtccgtc 7 7 - 6 = 1 7 - 6 = 1

gtccgtc 7 Kein Shift möglich