The Dynamic k-Mismatch Problem

The text-to-pattern Hamming distances problem asks to compute the Hamming distances between a given pattern of length m and all length-m substrings of a given text of length n ? m. We focus on the well-studied k-mismatch version of the problem, where a distance needs to be returned only if it does not exceed a threshold k. Moreover, we assume n ? 2m (in general, one can partition the text into overlapping blocks). In this work, we develop data structures for the dynamic version of the k-mismatch problem supporting two operations: An update performs a single-letter substitution in the pattern or the text, whereas a query, given an index i, returns the Hamming distance between the pattern and the text substring starting at position i, or reports that the distance exceeds k. First, we describe a simple data structure with ??(1) update time and ??(k) query time. Through considerably more sophisticated techniques, we show that ??(k) update time and ??(1) query time is also achievable. These two solutions likely provide an essentially optimal trade-off for the dynamic k-mismatch problem with m^{?(1)} ? k ? ?m: we prove that, in that case, conditioned on the 3SUM conjecture, one cannot simultaneously achieve k^{1-?(1)} time for all operations (updates and queries) after n^{?(1)}-time initialization. For k ? ?m, the same lower bound excludes achieving m^{1/2-?(1)} time per operation. This is known to be essentially tight for constant-sized alphabets: already Clifford et al. (STACS 2018) achieved ??(?m) time per operation in that case, but their solution for large alphabets costs ??(m^{3/4}) time per operation. We improve and extend the latter result by developing a trade-off algorithm that, given a parameter 1 ? x ? k, achieves update time ??(m/k +?{mk/x}) and query time ??(x). In particular, for k ? ?m, an appropriate choice of x yields ??(?{mk}) time per operation, which is ??(m^{2/3}) when only the trivial threshold k = m is provided