Linear-Space LCS Enumeration for Two Strings

Comparing two strings to find common patterns that would be most informative of their relationships is a fundamental task in parsing them. The longest common subsequences (LCSs) are regarded as such common patterns, and the problem of efficiently finding one of them has long been studied [2, 3, 5, 6, 7, 8, 9, 10, 11, 13]. Here, a subsequence of a string is the sequence obtained from the string by deleting any number of elements at any position that is not necessarily contiguous. Hence, an LCS of two strings is a common subsequence obtained by deleting the least possible number of elements from the strings. For example, if $X=\mathrm{𝚊𝚌𝚍𝚍𝚊𝚍𝚊𝚌𝚋𝚌𝚋}$ and $Y=\mathrm{𝚌𝚊𝚌𝚌𝚋𝚊𝚊𝚍𝚌𝚊𝚍}$ are the target strings, then $\mathrm{𝚌𝚊𝚌𝚌𝚋}$ is one of the seven distinct LCSs of $X$ and $Y$. The six other LCSs are $\mathrm{𝚌𝚊𝚌𝚋𝚌}$, $\mathrm{𝚊𝚌𝚌𝚋𝚌}$, $\mathrm{𝚊𝚌𝚊𝚊𝚌}$, $\mathrm{𝚊𝚌𝚊𝚍𝚌}$, $\mathrm{𝚊𝚌𝚊𝚍𝚊}$, and $\mathrm{𝚊𝚌𝚍𝚊𝚍}$.

Given a pair of strings $X$ and $Y$ both of length $n$ and a string $Z$ of length less than $n$, it is easy to determine whether $Z$ is a common subsequence of $X$ and $Y$ in $O(n)$ time. In comparison, it is hard to determine whether $Z$ is an LCS of $X$ and $Y$. The reason is that we need to know the LCS length in advance. It was revealed [1, 4] that unless the strong exponential time hypothesis (SETH) does not hold, no algorithm can determine the LCS length of $X$ and $Y$ in $O(n^{2-\epsilon })$ time for any positive constant $\epsilon$. Therefore, we cannot find any LCS in $O(n^{2-\epsilon })$ time under SETH.

On the other hand, as is well known, finding an arbitrary LCS of $X$ and $Y$ is possible in $O(n^2)$ time and $O(n^2)$ space by the dynamic programming (DP) algorithm [13]. The space of size $O(n^2)$ consumed to store the LCS lengths for all pairs of a prefix of $X$ and a prefix of $Y$ can be treated as constituting a particular directed acyclic graph (DAG) such that any path from the source to the sink represents an LCS of $X$ and $Y$. This DAG is also useful in applications other than seeking a single arbitrary LCS because each LCS is represented by at least one of the paths from the source to the sink. If one considers only the problem of finding a single arbitrary LCS without intending a data structure representing all LCSs, Hirschberg [7] showed that $O(n)$ space is sufficient to solve the problem in the same $O(n^2)$ time as the DP algorithm. Excluding the read-only memory storing $X$ and $Y$, his algorithm with a slight modification performs only in $O(L(X,Y))$ space, where $L(X,Y)$ denotes the LCS length of $X$ and $Y$.

The advantage of $O(L(X,Y))$-space algorithms for finding an arbitrary LCS is that they perform without reserving $O(n^2)$ space, the size of which becomes pronounced when $n$ is large. Thus, a natural question that would come to mind is whether it is possible to design $O(L(X,Y))$-space algorithms that are as accessible to all LCSs as the DP algorithm in addition to the above advantage. As a part of the answer to this question, this article shows that an $O(L(X,Y))$-space algorithm is capable of enumerating all distinct LCSs with a delay time not significantly inferior to the running time of Hirschberg’s $O(L(X,Y))$-space algorithm [7] for finding a single arbitrary LCS. More precisely, the algorithm proposed in this article outputs each LCS in $O(n^2\log L(X,Y))$ time after the previous LCS is output, if any, which is inferior by a logarithmic factor of $L(X,Y)$. Enumeration is done by introducing a DAG, called the all-LCS graph, with each path from the source to the sink corresponding to a distinct LCS and vice versa. Since the size of the all-LCS graph is $O(n^2)$, which exceeds $O(L(X,Y))$, we design the proposed algorithm to somehow perform a depth-first search without explicitly constructing it.

For any sequences $S$ and $S^{\prime }$, let $S\circ S^{\prime }$ denote the concatenation of $S$ followed by $S^{\prime }$. For any sequence $S$, let $|S|$ denote the length of $S$, i.e., the number of elements in $S$. For any index $i$ with $1\le i\le |S|$, let $S[i]$ denote the $i$th element of $S$, so that $S=S[1]\circ S[2]\circ \mathrm{\cdots }\circ S[|S|]$. A subsequence of $S$ is obtained from $S$ by deleting zero or more elements at any positions not necessarily contiguous, i.e., the sequence $S[i_1]\circ S[i_2]\circ \mathrm{\cdots }\circ S[i_{\mathrm{\ell }}]$ for some length $\mathrm{\ell }$ with $0\le \mathrm{\ell }\le |S|$ and some $\mathrm{\ell }$ indices $i_1,i_2,\mathrm{\dots },i_{\mathrm{\ell }}$ with . For any indices $i$ and $i^{\prime }$ with $1\le i\le i^{\prime }+1\le |S|+1$, let $S[i:i^{\prime }]$ denote the contiguous subsequence $S[i]\circ S[i+1]\circ \mathrm{\cdots }\circ S[i^{\prime }]$ of $S$, where $S[i:i^{\prime }]$ with $i=i^{\prime }+1$ represents the empty subsequence. If $i=1$ (resp. $i^{\prime }=|S|$), then $S[i:i^{\prime }]$ is called a prefix (resp. suffix) of $S$.

A string is a sequence of characters over an alphabet set. For any strings $X$ and $Y$, a common subsequence of $X$ and $Y$ is a subsequence of $X$ that is a subsequence of $Y$. Let $L(X,Y)$ denote the maximum of $|Z|$ over all common subsequences $Z$ of $X$ and $Y$. Any common subsequence $Z$ of $X$ and $Y$ with $|Z|=L(X,Y)$ is called a longest common subsequence (an LCS) of $X$ and $Y$. The following lemma gives a typical recursive expression for the LCS length.

Let any algorithm that takes certain information, specified later, of an arbitrary pair of non-empty strings $X$ and $Y$ as input and uses only $O(L(X,Y))$ space to output all distinct LCSs of $X$ and $Y$, each represented by a specific form, one by one be called a linear-space LCS enumeration algorithm. We assume that the information of $X$ and $Y$ given to the algorithm consists of $|X|$, $|Y|$, and $O(1)$-time access to check whether $X[i]=Y[j]$ or not for any pair of indices $i$ and $j$ with $1\le i\le |X|$ and $1\le j\le |Y|$ with no space consumption. The worst-case time between outputting one LCS and the next LCS is called the delay time of the algorithm. This article aims to propose a linear-space LCS enumeration algorithm with $O(|X||Y|\log L(X,Y))$ delay time.

Let any index pair $(i,j)$ such that $1\le i\le |X|$, $1\le j\le |Y|$, and $X[i]=Y[j]$ be called a match. For convenience, we sometimes treat $X[0]$ and $Y[0]$ (resp. $X[|X|+1]$ and $Y[|Y|+1])$ as virtual elements of $X$ and $Y$, respectively, both of which are identical to a virtual character, say $\mathrm{♯}$ (resp. $\$$), that appears in neither $X$ nor $Y$, so that $(0,0)$ (resp. $(|X|+1,|Y|+1)$) can be treated as a virtual match. We use src and snk to denote $(0,0)$ and $(|X|+1,|Y|+1)$, respectively. For any match $w$, let $i_w$ and $j_w$ denote the indices such that $(i_w,j_w)=w$. Furthermore, let the diagonal coordinate of $w$ be $j_w-i_w$, by treating any match as a grid point on a two-dimensional plane. For any matches $w$ and $w^{\prime }$, let (resp. $w\le w^{\prime }$) mean that both and (resp. $i_w\le i_{w^{\prime }}$ and $j_w\le j_{w^{\prime }}$). For any non-virtual match $w$, we call the character that is identical to both $X[i_w]$ and $Y[j_w]$ the character corresponding to $w$. Similarly, for any sequence $W$ of non-virtual matches, we call the concatenation of the characters corresponding to $W[k]$ for all indices $k$ from $1$ to $|W|$ in this order the string corresponding to $W$.

Let us call any sequence $W$ of $L(X,Y)$ non-virtual matches with an LCS-match sequence, because the string corresponding to $W$ is an LCS of $X$ and $Y$. For convenience, we sometimes treat $\text{src}(=(0,0))$ and $\text{snk}(=(|X|+1,|Y|+1))$ as virtual elements $W[0]$ and $W[L(X,Y)+1]$ of any LCS-match sequence $W$, respectively. Although any LCS $Z$ of $X$ and $Y$ has at least one LCS-match sequence $W$ with $Z$ as the corresponding string, two or more such LCS-match sequences $W$ may exist. Hence, the problem of enumerating LCSs is not equivalent to the problem of enumerating LCS-match sequences. As the representative of LCS-match sequences $W$ having the same corresponding strings, we consider the one such that for any index $k$ with $1\le k\le L(X,Y)$, $X[1:i_{W[k]}]$ and $Y[1:j_{W[k]}]$ are the shortest prefixes of $X$ and $Y$ with the string corresponding to $W[1:k]$ as a subsequence, respectively. We call any such LCS-match sequence front-leaning. Since any LCS $Z$ of $X$ and $Y$ has exactly one front-leaning LCS-match sequence $W$ with $Z$ as the corresponding string, the problem of enumerating LCSs is equivalent to the problem of enumerating front-leaning LCS-match sequences. Based on this observarion, we design the proposed linear-space LCS enumeration algorithm to output all distinct front-leaning LCS-match sequences one by one instead of outputting the corresponding LCSs.

This section proposes a linear-space LCS enumeration algorithm that outputs all distinct front-leaning LCS-match sequences of $X$ and $Y$ each in $O(|X||Y|\log L(X,Y))$ time.

Our approach to designing the algorithm considers a particular directed acyclic graph (DAG), which we call the all-LCS graph, such that each path from vertex $\text{src}(=(0,0))$ to vertex $\text{snk}(=(|X|+1,|Y|+1))$ represents a distinct front-leaning LCS-match sequence and vice versa, where each vertex in the graph is a different particular match. Relying on this DAG, we can enumerate LCSs by enumerating all paths from src to snk in a straightforward manner using depth-first search (DFS). The all-LCS graph we introduce is of size $O(|X||Y|)$, which exceeds the size of space allowed for any linear-space LCS enumeration algorithm. Our proposed algorithm overcomes this situation by simulating DFS on the all-LCS graph without explicitly constructing it. We define the all-LCS graph in Section 3.1 and propose a linear-space LCS enumeration algorithm by presenting how to simulate the DFS in Section 3.2.