Algorithms on Strings
Describing algorithms in a C-like language, this text presents examples related to the automatic processing of natural language, to the analysis of molecular sequences and to the management of textual databases.
TABLE OF CONTENTS Algorithms on Strings
8.4: Approximate Matching for Short Patterns
8.4 Approximate Matching for Short Patterns
The algorithm presented in this section is a method both very fast in practice and very simple to implement for short patterns. The method solves the problems presented in the previous sections in the bit-vector model introduced in Section 1.5. We first describe the method for the exact string searching, then we show how we can adapt it for dealing with the approximate string searching with mismatches and with the approximate string searching with differences. The principal advantage of this method is that it is flexible and so adapts to a large range of problems.
Exact string matching
We first present a technique for solving the problem of the exact search for all the occurrences of a string x inatext y, that is different from the methods already encountered in Chapters 1, 2, and 3.
We consider n + 1 vectors of m bits, 
, 
, , 
. The vector 
corresponds to the processing of the letter y[ j] of the text. It contains the information relative to the search on all the prefixes of x when their last position is aligned with the position j on the text (see Figure 8.12). It is defined by
for i = 0 , 1 , , m ? 1. So, [ m ? 1] = 0 if and only if x occurs at position j. The vector
Copyright Maxime Crochemore, Christophe Hancart, Thierry Lecroq 2007 under license agreement with Books24x7
