Efficient String Matching with Don’t-Care Patterns

This paper considers the extension of the methods of Aho and Corasick to deal with patterns involving more expressive descriptions, such as don’t-care (wild-card) symbols, complements, etc.

Abstract

The occurrences of a constant pattern in a given text string can be found in linear time using the famous algorithm of Knuth, Morris, and Pratt [KMP]. Aho and Corasick [AC] independently solved the problem for patterns consisting of a set of strings, where the occurrence of one member is considered a match. Both algorithms preprocess the pattern so that the text can be searched efficiently. This paper considers the extension of their methods to, deal with patterns involving more expressive descriptions, such as don't-care (wild-card) symbols, complements, etc. Such extensions are useful in the context of clever text-editors and the analysis of chemical compounds.The main result of this paper is an algorithm to deal efficiently with patterns containing a definite number of don't-care symbols. Our method is to collect "evidence" about the occurrences of the constant parts of the pattern in the text, using the algorithm of Aho and Corasick [AC]. We arrange the consequences of the intermediate results of the search in an array of small counters whose length is equal to that of the pattern. As soon as a match for the whole pattern is found, it is reported. If we assume that the counters can be incremented in parallel, the overall (time and space) complexity of the algorithm remains linear. Otherwise, the worst-case time complexity becomes quadratic, without changing the space requirements.We include here a discussion of why alternative ways to solve the problem, especially those trying to preserve the purely automaton-driven constructions of [KMP] and [AC], do not work. Finally, we describe a minor extension to an algorithm of Fischer and Paterson [FP]. Originally, it could deal with don't-cares in the text; now it can also handle complements of single characters within the same computational complexity.