Abstract
String searching is a very important component of many problems, including text editing, bibliographic retrieval, and symbol manipulation. Recent surveys of string searching can be found in [4, 18] . The string-matching problem consists of finding all occurrences of a pattern of length m in a text of length n. We generalize the problem allowing don't care symbols, the complement of a symbol, and any finite class of symbols. We solve this problem for one or more patterns, with or without mismatches. For small patterns the worst-case time is linear in the size of the text (we say that a pattern is small if m is bounded by a constant). The main idea is to represent the state of the search as a number, and each search step does a small number of arithmetic and logical operations, provided that the numbers are large enough to represent all possible states of the search. Hence, for m ~ w, being w the word size in bits of the computer used, we have an O(n) time algorithm using O(IZI) extra space and O(m + lY~I) preprocessing time, where Z denotes the alphabet. For string matching, empirical results show that the new algorithm compares favorably with the Knuth-Morris-Pratt (KMP) algorithm [24] for any pattern length and the Boyer-Moore (BM) algo-rithm [12] for short patterns (up to length 6). For patterns with don't care symbols and complement symbols, this is the first practical and efficient algorithm in the literature, and it can be generalized to any finite class of symbols or their complements. For searches with at most k mismatches, this algorithm is three times faster than any known algorithm for m < 9. The main properties of this class of algorithms are: • Simplicity: The preprocessing and the search are very simple, and only bitwise logical operations, shifts and additions are used. • No buffering: The text does not need to be stored. • Real time: The time delay to process one text character is bounded by a constant depending only on the pattern length. It is worth noting that the BM algorithm needs to buffer the text. All these properties indicate that this class of algorithm is suitable for hardware implementation. For these reasons, we believe this new approach is a valuable contribution to all applications dealing with text searching. A preliminary version of this article was presented in [9] .
Showing the abstract — retrieve the full paper via the Exa API.