Efficient pattern-matching with don't cares

Adam KalaiSODA 2002 · OpenReview

Abstract

We present a randomized algorithm for the string matching with don't cares problem. Based on the simple fingerprint method of Karp and Rabin for ordinary string matching [4], our algorithm runs in time O(n log m) for a text of length n and a pattern of length m and is simpler and slightly faster than the previous algorithms [3, 5, 1].
BibTeX
@inproceedings{kalai2002efficient,
  author = {Adam Kalai},
  title = {{Efficient pattern-matching with don't cares}},
  booktitle = {SODA},
  year = {2002},
  url = {https://openreview.net/forum?id=Qigj0SBTkwB},
}

Loading related content...

Figure