Verifying Candidate Matches in Sparse and Wildcard Matching

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^2 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(nlog2 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^2 m)$ time deterministic algorithm for Subset Matching and Tree Pattern Matching