Exploring the Gap Between LCS and LCStr

The Longest Common Subsequence (LCS) problem is one of the classical problems in computer science. Its first well-known quadratic-time dynamic programming solution was presented in 1974 by Wagner and Fischer [77]. In this problem, we are given two strings over the same alphabet and seek the length of the longest subsequence common to both strings, where a subsequence is obtained from a sequence by deleting zero or more elements. LCS has numerous applications, including in genetics and molecular biology [26, 30, 33, 80], optical character recognition (OCR) [42], and other domains. A wide range of algorithms has been proposed for solving LCS; see, for example, the surveys [21, 72].

Given its importance, many variants of LCS have been studied over the years. These include LCS for multiple strings (e.g., [1, 62, 79]), LCS under correlated sequence models [44], tree LCS (e.g., [11, 69]), weighted LCS (e.g., [10, 18]), the Longest Common Increasing Subsequence (e.g., [32, 27, 37]), constrained LCS (e.g., [13, 40, 46, 47, 57]), the Longest Common Parameterized Subsequence [45, 55, 63], and the Longest Common Palindromic Subsequence [16, 36, 61], among many other generalizations (e.g., [20, 22, 26, 54, 56]).

Considerable effort has also been devoted to identifying and exploiting structural properties of the input in order to design faster algorithms [14, 15, 38, 50, 53, 58, 70, 71, 83].

In the Longest Common Substring (LCStr) problem, the goal is to find a common substring of the input strings, rather than a subsequence. Equivalently, LCStr can be viewed as a variant of the LCS problem in which the common subsequence is required to be a substring of both input strings. The LCStr problem is a fundamental problem in string processing, with numerous applications [4, 31, 35, 43]. It admits a straightforward linear-time solution using a (generalized) suffix tree [48, 81]. The problem has also been studied in various models and settings, including small-space algorithms [75, 65, 19], dynamic strings [8, 7, 9, 28], packed string representations [29], LCStr with up to $k$ mismatches [41, 76, 64, 29], and LCStr with up to $k$ edits [6].

To explore the gap between the LCS and LCStr problems, we briefly review their time complexity, approximation algorithms, and multi-string variants. This serves as a baseline for analyzing the LCSS problem.

Abboud et al. [1] and Bringmann and Künnemann [25] showed that any subquadratic-time algorithm for LCS would refute the Strong Exponential Time Hypothesis (SETH). Abboud et al. [2] further strengthened this result by showing that even a strongly subquadratic-time algorithm for LCS would refute a natural, weaker variant of SETH defined over branching programs.

Moreover, Bringmann and Künnemann [23] conducted a systematic study of the multivariate complexity of LCS, taking into account a wide range of parameters that influence the running time (such as input size, the length of the shorter string, and the length of the LCS). For any class of instances obtained by bounding each parameter by a polynomial in the input size, they established corresponding SETH-based lower bounds.

To compute the Longest Common Substring of $k$ strings, Hui [52] showed that a (generalized) suffix tree can be exploited to obtain a linear-time algorithm.

The problem of finding the LCS of $k$ strings is commonly referred to as $k$-LCS. Maier [68] proved that $k$-LCS is NP-complete when $k$ is unbounded, even over an alphabet of size $3$. Over the years, several algorithms have been proposed for this problem. For example, Irving and Fraser [62] presented an algorithm with running time $O(kn{(n-\mathrm{\ell })}^{k-1})$, where $n$ is the common length of the input strings and $\mathrm{\ell }$ is the length of an LCS. For the special case of three strings, Wang and Zhu [78] proposed two algorithms with running times $O(n^2\delta )$ and $O(n+R\log n+R^2)$, where $\delta$ denotes the minimum number of deletions required to obtain a common subsequence, and $R$ is the number of matching triples $(x,y,z)$ such that $S_1[x]=S_2[y]=S_3[z]$. In the worst case, however, these approaches require $\mathrm{\Omega }(n^3)=\mathrm{\Omega }(n^k)$ time.

For LCStr, the existence of a linear-time exact algorithm immediately implies a linear-time approximation algorithm. Moreover, a sublinear-time approximation with a constant factor is unlikely, as it would yield a sublinear-time algorithm for testing equality between two strings.

For LCS, simple near-linear-time algorithms achieve either a $1/|\mathrm{\Sigma }|$-approximation or a $1/\sqrt{n}$-approximation, where $n$ is the input size and $\mathrm{\Sigma }$ is the alphabet. In recent years, several works have studied the approximation of LCS. Abboud and Rubinstein [3] explored connections between approximate LCS and circuit complexity. Rubinstein and Song [74] showed that a $(1/2+ϵ)$-approximation can be obtained in subquadratic time for two equal-length strings over a binary alphabet. This result was later improved by Akmal and Vassilevska Williams [5], who achieved a $(1/2+ϵ)$-approximation in subquadratic time for any constant-size alphabet. For large alphabets, HajiAghayi et al. [49] improved the $1/n^{0.5}$-approximation to $1/n^{0.498}$ while maintaining linear running time. Subsequently, Bringmann et al. [24] further improved the approximation ratio to $1/n^{0.4}$ and introduced a trade-off between the approximation ratio and the running time. In an unpublished manuscript, Nosatzki [73] described a linear-time algorithm achieving an approximation ratio of $1/n^{o(1)}$. Notably, all algorithms whose approximation guarantees depend on $n$ (rather than $|\mathrm{\Sigma }|$) are randomized.

The contrasting complexity landscape of LCS and LCStr indicates that restricting the search to substrings significantly simplifies the problem. Several variants of LCS aim to bridge this gap by requiring the common subsequence to include substrings; see, e.g., [17, 20].

Recently, Banerjee et al. [17] introduced the Longest Common Factor with Gaps ($k$-LCFg) problem, in which the common subsequence is composed of at most $k$ matching substrings, and the objective is to maximize their total length. They provide an algorithm with running time $\tilde{O}(n{m}^{1-1/3^{k-2}})$.

Benson et al. [20] defined the $LCSk$ problem, where the common subsequence must consist of substrings of length exactly $k$ in both input strings. Several algorithms have been proposed for $LCSk$ [20, 34, 51, 84], all of which have quadratic worst-case running time.

Both problems incorporate substrings into the subsequence structure, but in different ways: $k$-LCFg allows substrings of unbounded length but limits their number, whereas $LCSk$ allows an unbounded number of substrings, each of fixed length. This distinction becomes especially pronounced when $k=1$: in this case, $k$-LCFg reduces to LCStr, while $LCSk$ coincides with LCS.

Recall that LCStr can be viewed as a variant of LCS in which the common subsequence is required to be a substring of both input strings. Given the substantial gap in complexity between LCS and LCStr (and their variants), a natural question arises: which additional constraints on LCS lead to problems whose complexity remains closer to that of LCS rather than LCStr?

Requiring substrings of fixed length (as in $LCSk$) appears to preserve the complexity characteristics of LCS. In contrast, allowing substrings of arbitrary length (as in $k$-LCFg) can break the quadratic-time barrier, bringing the problem closer to LCStr in terms of complexity.

Notably, both $LCSk$ and $k$-LCFg require the subsequence to consist of substrings from both input strings. This raises a natural question: what happens if this requirement is imposed on only one of the strings? To address this question, we consider an intermediate variant between LCS and LCStr, in which the common subsequence is required to be a substring of one of the input strings. This problem, called the Longest Common Subsequence-Substring (LCSS), is defined as follows.

For example, let $S=\mathrm{cb}\text{ab}\mathrm{cbccb}\text{aab}\mathrm{ba}\text{c}\mathrm{aca}$ and $T=\text{abaabc}\mathrm{bac}$. Then $\mathrm{𝖫𝖢𝖲𝖲}(S,T)=6$, and one longest common subsequence-substring is abaabc.

In addition to its theoretical interest, the LCSS problem is motivated by applications in cybersecurity. In such settings, malware signatures are often fragmented and transmitted across multiple packets, making detection challenging [66]. Given a set of signatures separated by a designated symbol, one may wish to identify the longest signature that appears as a subsequence in observed data, effectively detecting a single, possibly fragmented, occurrence. A related problem, Dictionary Matching with a Few Gaps [12], focuses on detecting all occurrences of patterns from a dictionary. In contrast, the LCSS formulation targets the detection of a single (longest) fragmented pattern.

Li, Deka, and Deka [67] introduced the LCSS problem and proposed a naive quadratic-time algorithm. Observe that the longest prefix of a string $U$ that appears as a subsequence of $S$ can be computed in $O(n)$ time using a two-pointer technique: the pointer on $S$ advances at every step, while the pointer on $U$ advances only upon a match. Applying this procedure to every suffix of $T$ yields an $O(nm)$-time algorithm.

• $\mathrm{■}$

  We first show (in Section 3) that the LCSS problem has inherent quadratic-time complexity, up to subpolynomial factors, under the Strong Exponential Time Hypothesis (SETH), via a reduction from the Orthogonal Vectors problem. This lower bound indicates that the additional constraint imposed by LCSS, compared to LCS, does not lead to a computationally easier problem, and in particular does not bring its complexity closer to that of LCStr.

• $\mathrm{■}$

  We then show (in Section 4) that for instances where $\mathrm{𝖫𝖢𝖲𝖲}(S,T)$ is small, the running time can be improved to $O((n+m\mathrm{\ell })\log |\mathrm{\Sigma }|)$, where $n=|S|$, $m=|T|$, $\mathrm{\ell }=\mathrm{𝖫𝖢𝖲𝖲}(S,T)$, and $\mathrm{\Sigma }$ is the alphabet.

• $\mathrm{■}$

  Furthermore, we study (in Section 4.1) the LCSS problem for multiple strings (formally defined in Problem 15) in order to better understand its computational relationship to LCS and LCStr. Our results indicate that, in this setting, the problem behaves differently from both. In particular, for a constant number of strings $S_1,\mathrm{\dots },S_{k_1}$ and $T_1,\mathrm{\dots },T_{k_2}$, each of length $n$, we present an algorithm with running time $O(n\mathrm{\ell }\log |\mathrm{\Sigma }|)$, where $\mathrm{\ell }=\mathrm{𝖫𝖢𝖲𝖲}(S_1,\mathrm{\dots },S_{k_1},T_1,\mathrm{\dots },T_{k_2})$.

• $\mathrm{■}$

  Finally, we present (in Section 5) a $(1-\epsilon )$-approximation algorithm for LCSS that runs in near-linear time, matching the time complexity of LCStr up to logarithmic factors. To the best of our knowledge, no comparable approximation results are known for the LCS problem.

We describe hereafter a data structure that satisfies the requirements of the lemma. In the preprocess we employ the following technique. $S$ is divided into chunks $C_f$ of length $|\mathrm{\Sigma }|$ each (except for the last chunk which may be shorter). Chunk $C_f$ represents substring $S[f|\mathrm{\Sigma }|+1..(f+1)|\mathrm{\Sigma }|]$ for . For each chunk $C_f$, we maintain two self-balancing binary search trees (BST), each of size $|\mathrm{\Sigma }|$:

1. 1.

   ${\mathrm{𝖨𝖭}}_{C_f}$. For every $\sigma \in \mathrm{\Sigma }$, ${\mathrm{𝖨𝖭}}_{C_f}[\sigma ]$ stores a sorted array $\sigma OC{C}_{C_f}$ which stores the positions of all occurrences of $\sigma$ within the corresponding substring of $C_f$. The arrays are constructed by scanning the substring corresponding to $C_f$ and inserting each symbol into its respective array. We emphasize that for every $\sigma$ the length of the array $\sigma OC{C}_{C_f}$, is exactly the number of occurrences of $\sigma$ in the substring corresponding to $C_f$.

2. 2.

   ${\mathrm{𝖮𝖴𝖳}}_{C_f}$. For every $\sigma \in \mathrm{\Sigma }$, $nex{t}_{C_f}[\sigma ]$ stores the position of the first occurrence of $\sigma$ that is after the end of chunk $C_f$, i.e., in $S[(f+1)|\mathrm{\Sigma }|+1..n]$. If $\sigma$ does not occur in the rest of $S$, then $nex{t}_{C_f}[\sigma ]=n+1$. To fill the ${\mathrm{𝖮𝖴𝖳}}_{C_f}$ values for each $\sigma \in \mathrm{\Sigma }$ we scan the string $S$ in reverse, from the end to the beginning, while maintaining an additional self-balancing binary search tree, $Last$ which stores for each $\sigma$ that we already scanned, its most recent occurrence. When we reach the end of a chunk’s scope, i.e., position $(f+1)|\mathrm{\Sigma }|$, we copy the contents of $Last$ into ${\mathrm{𝖮𝖴𝖳}}_{C_f}$.

An example of the data structure constructed during preprocessing is shown in Figure 1.

Given a query of $\sigma \in \mathrm{\Sigma }$, and an index $i\ge 1$, we need to find the first occurrence of $\sigma$ in $S[i..n]$. We assume that $i\in [n]$, as otherwise the algorithm trivially returns $n+1$. Consider the chunk $C_f$ where $i\in C_f$, i.e., $f=\lfloor i/|\mathrm{\Sigma }|\rfloor$. We use ${\mathrm{𝖨𝖭}}_{C_f}[\sigma ]$ to access $\sigma OC{C}_{C_f}$ on which we perform a binary search on $\sigma OC{C}_{C_f}$ to find the smallest element that is at least $i$. In case there is no such element, return the value saved in ${\mathrm{𝖮𝖴𝖳}}_{C_f}[\sigma ]$, or $n+1$ if such a value does not exist.

The construction of each BST over $|\mathrm{\Sigma }|$ symbols requires $|\mathrm{\Sigma }|\log |\mathrm{\Sigma }|$ time. The time required to construct each $\sigma OC{C}_{C_f}$ is linear in its length, thus, all $O(|\mathrm{\Sigma }|)$ $\sigma OC{C}_{C_f}$ arrays within a chunk $C_f$, collectively store $|\mathrm{\Sigma }|$ symbols indices, are constructed in $O(|\mathrm{\Sigma }|\log |\mathrm{\Sigma }|)$ time. Given that there are $n/|\mathrm{\Sigma }|$ chunks, the total time required for constructing the sorted arrays is $O(n\log |\mathrm{\Sigma }|)$. The time complexity for the scan that the algorithm executes for filling the OUT arrays is also $O(n\log |\mathrm{\Sigma }|)$.

Finally, to answer a query, the algorithm uses (at most) two balanced binary search tree of size at most $|\mathrm{\Sigma }|$ and executes a binary search on an array of length $|\mathrm{\Sigma }|$. Thus, the time complexity of answering a query is $O(\log |\mathrm{\Sigma }|)$ $◀$

Let $𝒫$ be a maximization problem, and let $\text{OPT}(I)$ denote the optimal value of an instance $I$. An algorithm $𝒜$ is said to be a $(1-\epsilon )$-approximation for $𝒫$ (for $\epsilon >0$) if for every instance $I$, it returns a solution of value $𝒜(I)$ such that $(1-\epsilon )\text{OPT}(I)\le 𝒜(I)\le \text{OPT}(I)$. That is, the value of the solution returned by $𝒜$ is guaranteed to be at least a $(1-\epsilon )$-fraction of the optimal value.

The following lemma by Farach-Colton, Ferragina and Muthukrishnan [39] introduce a linear-time construction algorithm for a suffix tree of a string with polynomial integer alphabet.

Given a set of strings over an alphabet of size polynomial in the total input length, all suffix trees can be constructed in linear time, as stated in the following lemma. This will be useful in our algorithms.

The proof consists of two steps.

First, we rename the letters of each string so that each string gets its own alphabet of size at most its length. For every occurrence of a letter in the input, create a record $(i,a,p)$, where $i$ is the index of the string, $a=T_i[p]$, and $p$ is the position of this occurrence inside $T_i$. There are exactly $n$ such records.

We sort these records lexicographically by the pair $(i,a)$. Since $i\in [k_T]\subseteq [n]$ and $a\in [|\mathrm{\Sigma }|]\subseteq [n^c]$, both coordinates fit in $O(\log n)$ bits. Hence the sorting can be done in $O(n)$ time by radix sort.

We now scan the sorted list. For each fixed string $T_i$, whenever we encounter a new letter value $a$, we assign it the next rank in $\{1,2,\mathrm{\dots }\}$ among the distinct letters of $T_i$. Let $T_i^{\prime }$ be the resulting renamed string. This scan clearly takes $O(n)$ time. If ${\sigma }_i$ is the number of distinct letters in $T_i$, then $T_i^{\prime }$ is over the alphabet $\{1,2,\mathrm{\dots },{\sigma }_i\}$, where ${\sigma }_i\le m_i$. Moreover, the renaming preserves equality and inequality of letters inside each fixed string, so the suffix tree of $T_i$ is obtained from the suffix tree of $T_i^{\prime }$ by replacing the renamed letters by the original ones. Thus it is enough to construct the suffix trees of the strings $T_1^{\prime },\mathrm{\dots },T_{k_T}^{\prime }$.

Second, for every $i\in [k_T]$, append to $T_i^{\prime }$ a terminal symbol ${\$}_i$ that is smaller than all alphabet symbols and appears only once. Since we build each suffix tree separately, we may simply use the same fresh terminal symbol ${\$}_i=0$ for every $i$. Now $T_i^{\prime }0$ has length $m_i+1$ and its alphabet size is at most ${\sigma }_i+1\le m_i+1$. Therefore, by Lemma 3, the suffix tree of $T_i^{\prime }0$ can be built in $O(m_i)$ time.

Summing over all $i\in [k_T]$, the total time for this step is ${\sum }_{i=1}^{k_T}O(m_i)=O(n)$. Together with the $O(n)$ time of the renaming step, the overall running time is $O(n)$. Hence all suffix trees can be computed in total $O(n)$ time. $◀$

We begin with the correctness of the algorithm. We first note that the value of $a$ at any time is a length of some CSS of $S$ and $T$, and therefore the output of the algorithm is at most $\mathrm{𝖫𝖢𝖲𝖲}(S,T)$. On the other hand, let $T[i..i+\mathrm{\ell }-1]$ be a longest CSS. Consider the $i$th iteration of line Line 3. It is straightforward to see that by choosing greedily the first valid occurrence of a character at any inner iteration of Line 5, the algorithm obtains the longest possible prefix of $T[i..m]$ that is a subsequence of $S$. Therefore, the algorithm finds in the $i$th iteration of Line 3 a CSS of length at least $\mathrm{\ell }$. Thus, the output of the algorithm is exactly $\mathrm{𝖫𝖢𝖲𝖲}(S,T)$.

Regarding the complexities, the initialization of the data structure of Lemma 2 at Line 1 takes $O(n\log |\mathrm{\Sigma }|)$ time. It is clear that any outer iteration of Line 3 executes at most $\mathrm{\ell }+1$ iterations of the inner-loop of Line 5. Each iteration of Line 5 takes $O(\log |\mathrm{\Sigma }|)$ time, dominated by the invocation of the query on $D$. Thus, the time complexity of the algorithm is $O((n+m\mathrm{\ell })\log |\mathrm{\Sigma }|)$. The space requirement derives from Lemma 2. $◀$

We first analyze the approximation ratio. Let $T[i..i+\mathrm{𝖫𝖢𝖲𝖲}(S,T)-1]$ be a longest CSS. Let $i^{\prime }$ be the minimum $i^{\prime }\in P$ in the set $P$ such that $i^{\prime }\ge i$. By the density of $P$ we have that $i^{\prime }\le i+\epsilon \tilde{\mathrm{\ell }}\le i+\epsilon \mathrm{𝖫𝖢𝖲𝖲}(S,T)$ and therefore $i^{\prime }-i\le \epsilon \mathrm{𝖫𝖢𝖲𝖲}(S,T)$. Moreover, since $T[i..i+\mathrm{𝖫𝖢𝖲𝖲}(S,T)]$ is a subsequence of $S$, we also have that $X=T[i^{\prime }..i+\mathrm{𝖫𝖢𝖲𝖲}(S,T)]$ is a subsequence of $S$. By our assumption, when scanning the suffix $T[i^{\prime }..i^{\prime }+2\tilde{\mathrm{\ell }}-1]$ the algorithm finds at least the length $x=|X|$. Thus, the reported value must be at least $x\ge \mathrm{𝖫𝖢𝖲𝖲}(S,T)-(i^{\prime }-i)\ge \mathrm{𝖫𝖢𝖲𝖲}(S,T)-\epsilon \mathrm{𝖫𝖢𝖲𝖲}(S,T)=(1-\epsilon )\mathrm{𝖫𝖢𝖲𝖲}(S,T)$. On the other hand since the algorithm always reports a length of a CSS, clearly the reported value is at most $\mathrm{𝖫𝖢𝖲𝖲}(S,T)$.