Answers are grounded in this paper and cite their sources.
In the classic longest common substring (LCS) problem, we are given two strings S and T, each of length at most n, over an alphabet of size $σ$, and we are asked to find a longest string occurring as a fragment of both S and T. Weiner, in his seminal paper that introduced the suffix tree, presented an O(n log σ)-time algorithm for this problem [SWAT 1973]. For polynomially-bounded integer alphabets, the linear-time construction of suffix trees by Farach yielded an $O(n)$-time algorithm for the LCS problem [FOCS 1997]. However, for small alphabets, this is not necessarily optimal for the LCS problem in the word RAM model of computation, in which the strings can be stored in O(n log σ/log n ) space and read in O(n log σ/log n ) time. We show that, in this model, we can compute an LCS in time O(n log σ/ √log n), which is sublinear in n if σ=2o(√log n) (in particular, if $σ=O(1)$), using optimal space O(n log σ/log n). In fact, it was recently shown that this result is conditionally optimal [Kempa and Kociumaka, STOC 2025]. We then lift our ideas to the problem of computing a k-mismatch LCS, which has received considerable attention in recent years. In this problem, the aim is to compute a longest substring of S that occurs in T with at most k mismatches. Thankachan et al.~showed how to compute a k-mismatch LCS in O(n logᵏ n) time for $k=O(1)$ [J. Comput. Biol. 2016]. We show an O(n logk-1/2 n)-time algorithm, for any constant $k>0$ and irrespective of the alphabet size, using $O(n)$ space as the previous approaches. We thus notably break through the well-known n logᵏ n barrier, which stems from a recursive heavy-path decomposition technique that was first introduced in the seminal paper of Cole et al. [STOC 2004] for string indexing with k errors.
No takes yet. Share an insight, caveat, or question.
Charalampopoulos et al. (2021) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: