Efficient pattern-matching with don't cares

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].

REFERENCES

• 1: M. J. Fischer and M. S. Paterson, String Matching and other Products, in Complexity of Computation, R. M. Karp (editor), SIAM AMS Proceedings, 7, pp. 113-125, 1974.
• 2: Z. Galil, Open problems in stringology, Combinatorial problems on words, NATO ASI Series, Vol. F12, pp. 1-8, 1985.
• 3: P. Indyk, Faster Algorithms for String Matching Problems: Matching the Convolution Bound, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.166, November 08-11, 1998
• 4: Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
• 5: S. Muthukrishnan , Krishna Palem, Non-standard stringology: algorithms and complexity, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.770-779, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195457]
• 6: S. Muthukrishnan , H. Ramesh, String matching under a general matching relation, Information and Computation, v.122 n.1, p.140-148, Oct. 1995 [doi>10.1006/inco.1995.1144]