Space-Efficient \(k\)-Mismatch Text Indexes
Tomasz Kociumaka, Jakub Radoszewski · Society for Industrial and Applied Mathematics eBooks · 2026
A central task in string processing is text indexing, where the goal is to preprocess a text (a string of length \(n\)) into an efficient index (a data structure) supporting queries about the text. While the most fundamental exact pattern matching queries ask to find all the occurrences of a pattern (a string of length \(m\)) as substrings of the text, many applications call for approximate pattern matching queries, where the pattern may differ slightly from the matching substrings. A breakthrough in the extensive study of approximate text indexing came from Cole, Gottlieb, and Lewenstein (STOC 2004), who proposed \(k\)-errata trees — a family of text indexes supporting several closely related flavors of approximate pattern matching queries. In particular, \(k\)-errata trees yield an elegant solution to \(k\)-mismatch queries, where the similarity is quantified using an upper bound \(k \ge 1\) on the Hamming distance between the pattern and its approximate occurrences. The resulting \(k\)-mismatch index uses \(\mathcal{O}(n \log^{k} n)\) space and answers a query for a length-\(m\) pattern in \(\mathcal{O}(\log^{k} n \log \log n + m + \texttt{occ})\) time, where \(\texttt{occ}\) is the number of approximate occurrences.