2017/04/05 by Paweł Gawrychowski, Przemysław Uznański, Gawrychowski, Paweł +1
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1704.01311
openalex publication_date 2017/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a pattern of length m and a text of length n, the goal in k-mismatch pattern matching is to compute, for every m-substring of the text, the exact Hamming distance to the pattern or report that it exceeds k. This can be solved in either \widetildeO(n √(k)) time as shown by Amir et al. [J. Algorithms 2004] or \widetildeO((m + k2) ⋅ n/m) time due to a result of Clifford et al. [SODA 2016]. We provide a smooth time trade-off between these two bounds by designing an algorithm working in time \widetildeO( (m + k √(m)) ⋅ n/m). We complement this with a matching conditional lower bound, showing that a significantly faster combinatorial algorithm is not possible, unless the combinatorial matrix multiplication conjecture fails.