Verifying candidate matches in sparse and wildcard matching

Abstract

(MATH) This paper obtains the following results on pattern matching problems in which the text has length n and the pattern has length m. An O(nlog m) time deterministic algorithm for the String Matching with Wildcards problems, even when the alphabet is large. An O(klog² m) time Las Vegas algorithm for the Sparse String Matching with Wildcards problem, where k«n is the number of non-zeros in the text. We also give Las Vegas algorithms for the higher dimensional version of this problem. As an application of the above, an O(nlog² m) time Las Vegas algorithm for the Subset Matching and Tree Pattern Matching problems and a Las Vegas algorithm for the Geometric Pattern Matching problem. Finally, an O(nlog² m) time deterministic algorithm for Subset Matching and Tree Pattern Matching. The crucial new idea underlying the first three results above is that of confirming matches by convolving vectors obtained by coding characters in the alphabet with non-boolean (i.e. rational or even complex) entries; in contrast, almost all previous pattern matching algorithms consider only boolean codes for the alphabet. The crucial new idea underlying the fourth result is a simpler method of shifting characters which ensures that each character occurs as a singleton in some shift.