2015/08/04 by Raphaël Clifford, Allyx Fontaine, Clifford, Raphaël +7 · 3 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1508.00731
openalex publication_date 2015/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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: 1) Our first result is a deterministic O(n k2logk / 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 by Amihood Amir et al. 2) We then give a randomised and online algorithm which runs in the same time complexity but requires only O(k2polylog m) space in total. 3) Next we give a randomised (1+ε)-approximation algorithm for the streaming k-mismatch problem which uses O(k2polylog m / ε2) space and runs in O(polylog m / ε2) worst-case time per arriving symbol. 4) Finally we combine our new results to derive a randomised O(k2polylog m) space algorithm for the streaming k-mismatch problem which runs in O(√(k)logk + polylog m) worst-case time per arriving symbol. This improves the best previous space complexity for streaming k-mismatch from FOCS 2009 by Benny Porat and Ely Porat by a factor of k. We also improve the time complexity of this previous result by an even greater factor to match the fastest known offline algorithm (up to logarithmic factors).