Efficient Pattern-Matching with Don’t Cares
- Adam Tauman Kalai
SODA '02 Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms |
Published by ACM Press
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].