Pattern Matching Algorithms with Don't Cares.

In this paper, we present algorithms for pattern matching, where either the pattern P or the text T can contain “don’t care” characters. If the pattern P contains don’t care characters, then we can solve the pattern matching problem in O(n +m + α) time, where α is the total number of occurrences of the component subpatterns. We also can handle online queries, given an O(n) preprocessing time, requiring O(m + α) time per query. If, on the other hand, the text T contains don’t care characters, then we can solve the problem in O(n +m + |occ(P)|) time where |occ(P)| is the total number of occurrences of P in T . The assumption that we make in this case is that the length of each component sub-text is greater than the length of the pattern.