24-09-2013, 04:29 PM
BOYER-MOORE ALGORITHM
BOYER-MOORE.docx (Size: 34.61 KB / Downloads: 20)
Main features
performs the comparisons from right to left;
preprocessing phase in O(m+) time and space complexity;
searching phase in O(mn) time complexity;
3n text character comparisons in the worst case when searching for a non periodic pattern;
O(n / m) best performance.
Description
The Boyer-Moore algorithm is considered as the most efficient string-matching algorithm in usual applications. A simplified version of it or the entire algorithm is often implemented in text editors for the «search» and «substitute» commands.
The algorithm scans the characters of the pattern from right to left beginning with the rightmost one. In case of a mismatch (or a complete match of the whole pattern) it uses two precomputed functions to shift the window to the right. These two shift functions are called the good-suffix shift (also called matching shift and the bad-character shift (also called the occurrence shift).
Assume that a mismatch occurs between the character x[i]=a of the pattern and the character y[i+j]=b of the text during an attempt at position j.
Then, x[i+1 .. m-1]=y[i+j+1 .. j+m-1]=u and x[i] y[i+j]. The good-suffix shift consists in aligning the segment y[i+j+1 .. j+m-1]=x[i+1 .. m-1] with its rightmost occurrence in x that is preceded by a character different from x[i] (see figure 13.1).