Skip to main content

Simple Deterministic Wildcard Matching

Peter Clifford, Rapha?Simple Deterministic Wildcard Matching. Information Processing Letters, . ISSN 0020-0190. December 2006. PDF, 103 Kbytes.


We present a simple and fast deterministic solution to the \emph{string matching with don't cares} problem. The task is to determine all positions in a text where a pattern occurs, allowing both pattern and text to contain single character wildcards. Our algorithm takes $O(n\log{m})$ time for a text of length $n$ and a pattern of length $m$ and in our view is conceptually simpler than previous approaches.

Bibtex entry.

Publication Admin