作者
Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, Tatiana Starikovskaya
发表日期
2016
图书
Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms
页码范围
2039-2052
出版商
Society for Industrial and Applied Mathematics
简介
We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and every m-length substring of a text of length n, as long as that Hamming distance is at most k. Where the Hamming distance is greater than k at some alignment of the pattern and text, we simply output “No”.
We study this problem in both the standard offline setting and also as a streaming problem. In the streaming k-mismatch problem the text arrives one symbol at a time and we must give an output before processing any future symbols. Our main results are as follows:
- Our first result is a deterministic O(nk2 log k/m + n polylog m) time offline algorithm for k-mismatch on a text of length n. This is a factor of k improvement over the fastest previous result of this form from SODA 2000 [9, 10].
- We then give a randomised and online algorithm …
学术搜索中的文章
R Clifford, A Fontaine, E Porat, B Sach, T Starikovskaya - Proceedings of the twenty-seventh annual ACM-SIAM …, 2016