We consider the classical exact multiple string matching problem. Our solution is based on @math -grams combined with pattern superimposition, bit-parallelism and alphabet size reduction. We discuss the pros and cons of the various alternatives of how to achieve best combination. Our method is closely related to previous work by (, 2006). The experimental results show that our method performs well on different alphabet sizes and that they scale to large pattern sets.
Perhaps the most famous solution to the multiple pattern matching problem is the Aho--Corasick (AC) @cite_19 algorithm, which works in linear time (prefix-based approach). It builds a pattern trie with extra (failure) links and actually generalizes the Knuth--Morris--Pratt algorithm @cite_23 for a single pattern. More precisely, AC total time is @math , where @math , the sum of pattern lengths, is the preprocessing cost, and @math is the total number of pattern occurrences in @math . Recently Fredriksson and Grabowski @cite_21 showed an average-optimal filtering variant of the classic AC algorithm. They built the AC automaton over superimposed subpatterns, which allows to sample the text characters in regular distances, not to miss any match (i.e., any verification). This algorithm is based on the same ideas as the current work.
@cite_19 @cite_21 @cite_23
2098102002 1985108724
The exact string matching problem is to find the occurrences of a pattern of length m from a text of length n symbols. We develop a novel and unorthodox filtering technique for this problem. Our method is based on transforming the problem into multiple matching of carefully chosen pattern subsequences. While this is seemingly more difficult than the original problem, we show that the idea leads to very simple algorithms that are optimal on average. We then show how our basic method can be used to solve multiple string matching as well as several approximate matching problems in average optimal time. The general method can be applied to many existing string matching algorithms. Our experimental results show that the algorithms perform very well in practice. An algorithm is presented which finds all occurrences of one given string within another, in running time proportional to the sum of the lengths of the strings. The constant of proportionality is low enough to make this algorithm of practical use, and the procedure can also be extended to deal with some more general pattern-matching problems. A theoretical application of the algorithm shows that the set of concatenations of even palindromes, i.e., the language @math , can be recognized in linear time. Other algorithms which run even faster on the average are also considered.