Scribd
Upload
60 views16 pages

Boyer-Moore String Matching Explained

The Boyer-Moore string matching algorithm preprocesses the pattern P and searches for occurrences of P in text T from right to left. It uses two rules - the Bad Character Rule and Good Suffix Rule - to determine how far to shift the pattern P when a mismatch occurs, allowing for shifts of multiple characters. This sublinear shifting property allows Boyer-Moore to have better performance than naive substring search in practice, though it has a worst case running time of O(nm) like other algorithms.

Uploaded by

vivek patel
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
60 views16 pages

Boyer-Moore String Matching Explained

The Boyer-Moore string matching algorithm preprocesses the pattern P and searches for occurrences of P in text T from right to left. It uses two rules - the Bad Character Rule and Good Suffix Rule - to determine how far to shift the pattern P when a mismatch occurs, allowing for shifts of multiple characters. This sublinear shifting property allows Boyer-Moore to have better performance than naive substring search in practice, though it has a worst case running time of O(nm) like other algorithms.

Uploaded by

vivek patel
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Boyer Moore Algorithm

What Its About


A String Matching Algorithm Preprocess a Pattern P (|P| = m) For a text T (| T| = n), find all of the

occurrences of P in T

Right to Left
Matching the pattern from right to left For a pattern abc:

T: P:

bbacdcbaabcddcdaddaaabcbcb abc

Worst case is still O(n m)

The Bad Character Rule (BCR)


On a mismatch between the pattern and the

text, we can shift the pattern by more than one place.

Sublinearity!
ddbbacdcbaabcddcdaddaaabcbcb acabc

BCR Preprocessing
A table, for each position in the pattern and a

character, the size of the shift. O(m ||) space. O(1) access time. 1 2 3 4 5 a b a c b: a 1 1 3 3 3 1 2 3 4 5 b 2 2 2 5

BCR - Summary
On a mismatch, shift the pattern to the right

until the first occurrence of the mismatched char in P.


Still O(n m) worst case running time:

T: aaaaaaaaaaaaaaaaaaaaaaaaa P: abaaaa

The Good Suffix Rule (GSR)


We want to use the knowledge of the

matched characters in the patterns suffix.


If we matched S characters in T, what is (if

exists) the smallest shift in P that will align a sub-string of P of the same S characters ?

GSR (Case 1)
Example 1 how much to move:

T: bbacdcbaabcddcdaddaaabcbcb P: cabbabdbab cabbabdbab

GSR (Case 2)
Example 2 what if there is no alignment:

T: bbacdcbaabcbbabdbabcaabcbcb P: bcbbabdbabc bcbbabdbabc

GSR - Detailed
We mark the matched sub-string in T with t

and the mismatched char with x


1. In case of a mismatch: shift right until the

first occurrence of t in P such that the next char y in P holds yx


2. Otherwise, shift right to the largest prefix of

P that aligns with a suffix of t.

Boyer Moore Algorithm


Preprocess(P)

k := m

while (k n) do

Match P and T from right to left starting at k If a mismatch occurs: shift P right (advance k) by max(good suffix rule, bad char rule). else, print the occurrence and shift P right (advance k) by the good suffix rule.

Algorithm Correctness
The bad character rule shift never misses a

match
The good suffix rule shift never misses a

match

Preprocessing the GSR L(i)


L(i) The biggest index j, such that j < m and

prefix P[1..j] contains suffix P[i..m] as a suffix but not suffix P[i-1..m]
1 2 3 4 5 6 7 8 9 10 11 12 13

P: b b a b b a a b b c a b b L: 0 0 0 0 0 0 0 0 0 0 9 0 12

Preprocessing the GSR l(i)


l(i) The length of the longest suffix of P[i..m]

that is also a prefix of P

P: b b a b b a a b b c a b b l: 2 2 2 2 2 2 2 2 2 2 2 1

Using L(i) and l(i) in GSR


If mismatch occurs at position m, shift P by 1
If a mismatch occurs at position i-1 in P:

If L(i) > 0, shift P by m L(i) else shift P by m l(i)

If P was found, shift P by m l(2)

Boyer Moore Worst Case Analysis


Assume P consists of m copies of a single

char and T consists of n copies of the same char:

T: aaaaaaaaaaaaaaaaaaaaaaaaa P: aaaaaa
Boyer Moore Algorithm runs in (m n) when

finding all the matches

You might also like