Università di Pisa,
Italyalessio.conte@unipi.ithttps://orcid.org/0000-0003-0770-2235/ Università
di Pisa, Italyroberto.grossi@unipi.ithttps://orcid.org/0000-0002-7985-4222/
National Institute of Informatics,
Japanpunzi@nii.ac.jphttps://orcid.org/0000-0001-8738-1595/ National Institute
of Informatics, Japanuno@nii.ac.jphttps://orcid.org/0000-0001-7274-279X/
Alessio Conte, Roberto Grossi, Giulia Punzi, and Takeaki Uno [500]Mathematics
of computing Combinatorial algorithms [500]Information systems Structured text
search John Q. Open and Joan R. Access 2 42nd Conference on Very Important
Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging,
United Kingdom 42 23

# A Compact DAG for Storing and Searching Maximal Common Subsequences

Alessio Conte  Roberto Grossi  Giulia Punzi  Takeaki Uno

###### Abstract

_Maximal Common Subsequences_ (MCSs) between two strings $X$ and $Y$ are
subsequences of both $X$ and $Y$ that are maximal under inclusion. MCSs relax
and generalize the well known and widely used concept of Longest Common
Subsequences (LCSs), which can be seen as MCSs of maximum length. While the
number both LCSs and MCSs can be exponential in the length of the strings,
LCSs have been long exploited for string and text analysis, as simple compact
representations of all LCSs between two strings, built via dynamic programming
or automata, have been known since the ’70s. MCSs appear to have a more
challenging structure: even listing them efficiently was an open problem open
until recently, thus narrowing the complexity difference between the two
problems, but the gap remained significant. In this paper we close the
complexity gap: we show how to build DAG of polynomial size—in polynomial
time—which allows for efficient operations on the set of all MCSs such as
enumeration in Constant Amortized Time per solution (CAT), counting, and
random access to the $i$-th element (i.e., rank and select operations). Other
than improving known algorithmic results, this work paves the way for new
sequence analysis methods based on MCSs.

###### keywords:

Maximal common subsequence, DAG, Compact data structures, Enumeration,
Constant amortized time, Random access

###### category:

##  1 Introduction

The _Longest Common Subsequence_ (LCS) [23, 3, 10, 14] have thoroughly been
studied in a plethora of string comparison application domains, like spelling
error correction, molecular biology, and plagiarism detection, to name a few.
The LCS is a special case of _Maximal Common Subsequence_ (MCS) for any two
strings $X,Y$: it is a string $S$ that is a subsequence of both $X$ and $Y$,
and is inclusion-maximal, namely, no other string $S^{\prime}$ containing $S$
is also a common subsequence of $X$ and $Y$. The set of all MCSs for $X$ and
$Y$ is denoted by $\mathit{MCS}(X,Y)$. For example,
$\mathit{MCS}(X,Y)=\\{\mathtt{T}\mathtt{A}\mathtt{C}\mathtt{A},\mathtt{G}\\}$
for $X=\mathtt{T}\mathtt{C}\mathtt{A}\mathtt{C}\mathtt{A}\mathtt{G}$ and
$Y=\mathtt{G}\mathtt{T}\mathtt{A}\mathtt{C}\mathtt{T}\mathtt{A}$, whereas
$\mathtt{T}\mathtt{C}\mathtt{A}\not\in\mathit{MCS}(X,Y)$ as it is contained in
$\mathtt{T}\mathtt{A}\mathtt{C}\mathtt{A}$, and the latter is also the only
LCS. A crucial observation is the following: if $S$ is a common subsequence,
it is always contained in some MCS but this is not necessarily true for LCS
(e.g. $S=\mathtt{G}$ is not contained in
$\mathtt{T}\mathtt{A}\mathtt{C}\mathtt{A}$).

In general, LCSs only provide us with information about the longest possible
alignment between two strings, while MCSs offer a different range of
information, possibly revealing slightly smaller but alternative alignments.
For very long strings an MCS may be just slightly shorter than an LCS but
provide information on parts of the strings not found by LCSs. In principle,
MCS could provide helpful information in all the applications where LCS are
used.

While there is a quadratic conditional lower bound for the computation of LCS,
based on the Strong Exponential Time Hypothesis [1], no such bound exists for
MCS: actually, an MCS between two strings of length $n$ can be extracted in
$O(n\sqrt{\log n/\log\log n})$ time [20]. Moreover it is NP-hard to compute
the LCS of an arbitrary number of strings [13], whereas a recent polynomial-
time algorithm for extracting an MCS from multiple strings exists [9]. It is
worth noting that even though there are a few more different approaches in the
literature to find LCS or common subsequences with some kind of constraints
(e.g. common subsequence trees [11], common subsequence automata [6]), the
above observations motivate further investigation to directly deal with MCS.

In this paper we proceed along that direction, and consider the problem of
storing and searching the set $\mathit{MCS}(X,Y)$. The main hurdle is that
$\mathit{MCS}(X,Y)$ could contain an exponential number of distinct strings
[5]: consequently, any trie-based or immediate automaton representation would
require exponential time and space for its construction. We improve
significantly over this direction as we list in our contributions, where
$n=\max\\{|X|,|Y|\\}$ and $\sigma$ is the size of the alphabet $\Sigma$ for
$X$ and $Y$:

  * •

We introduce a labeled compact direct acyclic graph $\textsf{MDAG}(X,Y)$ (for
$MCS$ $DAG$) that represents the strings in $\mathit{MCS}(X,Y)$ in polynomial
space $O(n^{3}\sigma)$ and can be built in polynomial time $O(n^{3}\sigma\log
n)$.

  * •

For any string $P$, we show how $\textsf{MDAG}(X,Y)$ can search the strings
with prefix $P$ from $\mathit{MCS}(X,Y)$ and report them in lexicographic
order, in $O(|P|\log\sigma+\mathit{occ})$ time, where $\mathit{occ}$ is the
number of reported strings.

  * •

For any integer $1\leq i\leq|\mathit{MCS}(X,Y|$, we show how
$\textsf{MDAG}(X,Y)$ with input $i$ can select the $i$th string $S$ in
lexicographic order from $\mathit{MCS}(X,Y)$, in $O(|S|\log\sigma)$ time; the
inverse operation of rank for input $S$ is supported in the same complexity,
where $i$ is returned.

  * •

We can list all the strings from $\mathit{MCS}(X,Y)$ lexicographically in
constant amortized time (CAT), namely, $O(|\mathit{MCS}(X,Y)|)$ time.

In Section 3 we implement $\textsf{MDAG}(X,Y)$ as a direct acyclic graph (DAG)
where the only zero indegree node is the source $s$ and the only zero
outdegree node is the target $t$. Each edge is labeled with a character from
the alphabet, so that any two outgoing edges from the same node have different
characters as labels. Moreover, each $st$-path corresponds to a string in
$\mathit{MCS}(X,Y)$, obtained by concatenating the characters on the edge
traversed along the $st$-path; vice versa, each string in $\mathit{MCS}(X,Y)$
is spelled out by an $st$-path. In order to define and build
$\textsf{MDAG}(X,Y)$ we use some properties on MCSs previously introduced in
[5] and described in Section 2, plus some new ideas to keep the size of MDAG
polynomial. As a result, after MDAG has been built and its unary paths have
been compacted, the aforementioned operations can be implemented in a simple
way, as shown in Section 4.

Finally, we observe that labels in $\textsf{MDAG}(X,Y)$ may not have constant
size each, so of course printing each reported string may require more than
constant time. However, our algorithms are able to report a compressed form of
the output by simply printing the changes, similarly to [21]. On the other
hand, we recall that the complexity of the algorithms should not measure the
printing procedures, as formalized by Frank Ruskey [18, Section 1.7] in the
“Don’t Count the Output Principle”, but rather the amount of data change that
takes place. As the latter takes constant time per solution, we have CAT
complexity.

Related work. Maximal common subsequences were first introduced in [8], in the
context of LCS approximation. The first algorithm for finding an MCS between
two strings was presented in [19], and subsequently refined in [20]. The
latter algorithm finds an MCS between two strings of length $n$ in
$O(n\sqrt{\log n/\log\log n})$. These algorithms can be also used to extend a
given sequence to a maximal one in the same time, and to check whether a given
subsequence is maximal in $O(n)$ time. In [9] the authors considered the
problem of finding an MCS of $m>2$ strings of total length $n$, and were able
to solve this in $O(mn\log n)$ time and $O(n)$ space. As for MCS enumeration,
[5] showed that this task can be performed in $O(n\log n)$ delay and quadratic
space.

The automaton approach has been used in literature to deal with subsequence-
related problems. The Directed Acyclic Subsequence Graph (DASG) introduced in
[2] is an automaton which accepts all subsequences of a given string $S$.
Given a set of strings, it can also be generalized to accepting subsequences
of any string in the set. Later, the common subsequence automata (CSA) was
introduced [7, 6, 22], which instead accepts _common_ subsequences of a set of
strings. Such automaton is similar to the common subsequence tree of [11], and
it can also be used to find a longest common subsequence between two strings
[15]. Binary decision diagrams such as ZDD [16] and SeqBDD [12] could
potentially be employed to compactly store $\mathit{MCS}(X,Y)$ but their
worst-case behaviour typically involves exponential construction time and
space.

We stress that it is not straightforward to efficiently adapt all of these
structures to the MCS problem: indeed, figuring out which of the accepted
strings are subsequences of each other is not an immediate task. We therefore
opted for a different approach, directly defining and constructing an MCS
automaton, based on combinatorial properties specific to MCSs.

Preliminaries.  [String notation] A string $S$ over an alphabet $\Sigma$ (of
size $\sigma=|\Sigma|$) is a concatenation of any number of its characters.
The empty string is denoted with $\varepsilon$. For $i\in[0,|S|-1]$, character
$S[i]$ occurs at position $i$ of string $S$, and position
$\mathit{next}_{S}(c,i)$ denote the next occurrence of character $c$ after
position $i$ in string $S$, if it exists (otherwise,
$\mathit{next}_{S}(c,i)=|S|-1$). The notation $S_{<i}$ indicates $S[0,i-1]$,
and $S_{\leq i}$ indicates $S[0,i]$. We say that $S$ is a _subsequence_ of a
string $X$, denoted $S\subset X$, if there exist indices $0\leq
i_{0}<...<i_{|S|-1}<|X|$ such that $X[i_{k}]=S[k]$ for all $k\in[0,|S|-1]$. In
this case we also say that $X$ _contains_ $S$. Given two strings $X$ and $Y$,
a string $S$ is a common subsequence if $S\subset X$ and $S\subset Y$.
Furthermore, $S$ is a _Maximal Common Subsequence_ , denoted
$S\in\mathit{MCS}(X,Y)$, if it is a common subsequence which is _inclusion-
maximal_ : there is no string $T\neq S$ such that $S\subset T\subset X,Y$.
[Graph notation] Given a directed graph $G=(V,E)$, we define the in-neighbors
of a node $v\in V$ as $N^{-}(v)=\\{u\in V\ |\ (u,v)\in E\\}$, and the out-
neighbors as $N^{+}(v)=\\{v\in V\ |\ (v,z)\in E\\}$; the in-degree is
$d^{-}(v)=|N^{-}(v)|$ and the out-degree is $d^{+}(v)=|N^{+}(v)|$. A subgraph
of graph $G=(V,E)$ is a graph $H=(W,F)$ such that $W\subseteq V$ and
$F\subseteq E$. A _path_ $P$ in a graph $G=(V,E)$ is a sequence of distinct
adjacent nodes: $P=u_{1}...u_{k}$ where $u_{i}\in V$ for all $i$, $u_{i}\neq
u_{j}$ for all $i\neq j$, and $(u_{i},u_{i+1})\in E$ for all $i$. $P$ is
called an $u_{1}u_{k}$-path. A path where the first and last nodes coincide is
called a _cycle_. A directed graph with no cycles is called a directed acyclic
graph, or _DAG_.

##  2 Structure of MCSs

In this section, we show known properties of MCSs which will be at the base of
MDAG. Firstly, we show how to naturally represent all the strings in
$\mathit{MCS}(X,Y)$ for any two given strings $X$ and $Y$, using a finite-
state automaton $A$ corresponding to a DAG with a single source $s$ and a
single target $t$, where each edge is labeled with a character of the alphabet
$\Sigma$; we show that $st$-paths in $A$ have a one-to-one correspondence with
the strings in $\mathit{MCS}(X,Y)$. Secondly, we recall and contextualize some
useful properties of MCSs proven in [5].

###  2.1 Modeling MCS as an Exponentially Large DAG

We here define a deterministic finite-state automaton $A$ that accepts the
strings in $\mathit{MCS}(X,Y)$. It is more convenient to define it directly as
an equivalent DAG, using the extended alphabet $\Sigma^{\prime}=\Sigma\cup\$$,
where the dollar sign is a new special character to identify the end of an
MCS.

######  Definition 2.1.

The edge-labeled DAG $A=(V\cup\\{s,t\\},E,\ell(\cdot))$ is defined for two
input strings $X$ and $Y$ to store their set $\mathit{MCS}(X,Y)$, as follows:

  * •

Every node in $V\cup\\{s\\}$ corresponds to a distinct prefix of a string in
$\mathit{MCS}(X,Y)$, with $s$ called _source node_ corresponding to the empty
string prefix.

  * •

For any two nodes $u,u^{\prime}\in V$, let $P,P^{\prime}$ be their
corresponding two prefixes. Then, $P^{\prime}=Pc$ iff $(u,u^{\prime})\in E$
with label $\ell(u,u^{\prime})=c$.

  * •

For any node $u\in V$, if its corresponding prefix is a whole string
$P\in\mathit{MCS}(X,Y)$, then $(u,t)\in E$ with label $\ell(m,t)=\$$.

$s$$t$ACCCTAGAGGAGAGGAGGGG$$$$$

$s$$t$ACCCTAGAGGAG$G$

Figure 1: Left: edge-labeled DAG $A$ for strings $X=$ TCACAGAGA and $Y=$
ACCCGTAGG. We have
$\mathit{MCS}(X,Y)=\\{\texttt{ACAGG},\texttt{ACGAG},\texttt{CCAGG},\texttt{CCGAG},\texttt{TAGG}\\}$;
each $st$-path in $A$ corresponds to one of these. For instance, the topmost
path corresponds to ACAGG. Right: compact MDAG for the same strings.

Given DAG $A$, we have a bijection between the strings in $\mathit{MCS}(X,Y)$
and the labeled $st$-paths (see the left of Figure 1 for an example). Indeed,
it is immediate that any such path corresponds to a string in
$\mathit{MCS}(X,Y)$ due to the way edges are placed. Vice versa, by
definition, we cannot have two out-going edges from the same node that share
the same label. Therefore, each MCS has exactly one corresponding $st$-path.
Note that the property of the outgoing labels also implies that
$d^{+}(u)\leq\sigma$ for all $u\in V$, and therefore $|E|\leq\sigma|V|$. As
the number of nodes in $A$ is $\Omega(|\mathit{MCS}(X,Y)|)$, its size is
exponential in the worst case.

######  Remark 2.2.

$A$ can be seen as an acyclic deterministic finite-state automaton that
accepts the set $\mathit{MCS}(X,Y)$. We have one state for each prefix of a
string in $\mathit{MCS}(X,Y)$. Given two states $q,q^{\prime}$, respectively
corresponding to prefixes $P,P^{\prime}$ of strings in $\mathit{MCS}(X,Y)$,
the transition function $\delta$ is given by $\delta(q,c)=q^{\prime}$ if and
only if $P^{\prime}=Pc$.

###  2.2 Known Concepts on MCS Enumeration

We now present a summary of some concepts introduced in [5], which will be
used for our results. Let string $P$ be called a _valid prefix_ if there
exists a string $Q$ such that their concatenation is $PQ\in\mathit{MCS}(X,Y)$.
Given a valid prefix $P$, the set of characters $c$ such that $P\,c$ is still
a valid prefix are called _valid extensions_.

Finding valid extensions of $P$ is not straightforward. Let $P$ be a valid
prefix, and let $X_{\leq l}$ and $Y_{\leq m}$ be respectively the shortest
prefixes of $X$ and $Y$ that contain $P$ as a subsequence. Consider a pair of
positions $i>l$ and $j>m$, respectively in $X$ and $Y$, corresponding to the
same character, say, $c\in\Sigma$. In order to assess whether $c$ is a valid
extension, checking if $P\,c$ is a maximal common subsequence of $X_{\leq i}$
and $Y_{\leq j}$ is necessary, but not sufficient:

######  Example 2.3.

Consider $X=\texttt{TCACAG}$ and $Y=\texttt{TACGAT}$, with
$\mathit{MCS}(X,Y)=\\{\texttt{TACA},\texttt{TACG}\\}$.

$X$T$l$C$i$ACAG$Y$T$m$AC$j$GAT

Consider the valid prefix $\mathtt{T}$, for which $l=0$ and $m=0$. Let $i=1$
and $j=2$: these correspond to character $\mathtt{C}$, and clearly
$\mathtt{T}\mathtt{C}\in\mathit{MCS}(X_{\leq i},Y_{\leq
j})=\mathit{MCS}(\texttt{TC},\texttt{TAC})$. Still, $\mathtt{C}$ is not a
valid extension of valid prefix $\mathtt{T}$, as $\mathtt{T}\mathtt{C}$ is not
a prefix of any MCS.

To circumvent this problem, the set $\mathit{Ext}_{l,m}$ of _candidate
extensions_ is defined in [5]: this is a set of pairs of positions $(i,j)$,
with $i\geq l$ and $j\geq m$, whose definition relies solely on the pair
$(l,m)$. The membership of $(i,j)$ to $\mathit{Ext}_{l,m}$ completes the
characterization of valid extensions (see Theorem 3 in [5]):

  * •

Let $P$ be a valid prefix, and let $X_{\leq l}$ and $Y_{\leq m}$ be
respectively the shortest prefixes of $X$ and $Y$ that contain $P$ as a
subsequence.

  * •

Then $P\,c$ is a valid prefix if and only if the following two conditions
hold:

    1. 1.

There exists $i$ and $j$ such that $c=X[i]=Y[j]$ and
$P\in\mathit{MCS}(X_{<i},Y_{<j})$;

    2. 2.

This pair of positions satisfies $(i,j)\in\mathit{Ext}_{l,m}$.

More details on the construction of set $\mathit{Ext}_{l,m}$ are beyond the
scope of this paper, but they can be found in [5, Section 2.3], along with a
$O(\sigma\log n)$ time method for its computation. In Example 2.3, it is
$(i,j)\not\in\mathit{Ext}_{l,m}$.

$X$TATC$l$GAC$\ltimes_{T}$TC$Y$TGAC$m$GCTAC$\ltimes_{B}$

TCACAG$l$ATG$\ltimes_{T}$ACTCTG$m$GTAG$\ltimes_{B}$

Figure 2:  Left: Swings $(\ltimes_{T},\ltimes_{B})$ for valid prefix TAC in
strings $X=\texttt{TATCGACTC}$ and $Y=\texttt{TGACGCTAC}$. Consider swing
$\ltimes_{T}$: $\texttt{TAC}\not\in\mathit{MCS}(X_{\leq\ltimes_{T}}$, $Y_{\leq
m})$ since TGAC is a common subsequence (dashed). Right: Two prefixes, TCG
(solid blue) and ACG (dashed orange), both ending at solid red positions
$(l,m)$, and having the same swings $(\ltimes_{T},\ltimes_{B})$. The valid
extensions are the same (dotted green): A and T.

The notion of _swings_ is a key concept to quickly verify the first condition
above. Swings characterize the amount by which we can “move” a given character
occurrence while retaining maximality (see Figure 2, right). Let $X_{\leq l}$
and $Y_{\leq m}$ be respectively the shortest prefixes of $X$ and $Y$ that
contain $P$ as a subsequence. The _swing_ of $P$, denoted $\ltimes(P)$, is a
pair of integers $\ltimes_{T}(P)$ and $\ltimes_{B}(P)$, called respectively
_top_ and _bottom_ swings, given by

  * •

$\ltimes_{T}(P)=\min\\{i>l\ |\ P\not\in\mathit{MCS}(X_{\leq i},Y_{\leq m})\\}$

  * •

$\ltimes_{B}(P)=\min\\{j>m\ |\ P\not\in\mathit{MCS}(X_{\leq l},Y_{\leq j})\\}$

It follows from the definition that $P\in\mathit{MCS}(X_{<i},Y_{<j})\iff
i\leq\ltimes_{T}(P)\text{ and }j\leq\ltimes_{B}(P)$. Given the swings,
condition 1 can thus be checked in constant time [5].

Updating the swings when a character is added can be done in $O(\sigma)$ time,
provided that we can find in constant time the next occurrence of a character
$c$ after a given position in the strings; more importantly, this update does
not need knowledge of the whole prefix, but just the positions its final
character ($l_{N},m_{N}$) and their current swings.

##  3 Polynomial-Size MDAG

The construction of DAG $A$ satisfying the conditions of Definition 2.1 would
require exponential time and space: the number of nodes of $A$ is between
$\Omega(|\mathit{MCS}(X,Y)|)$ and $O(n|\mathit{MCS}(X,Y)|)$, so it can be
exponential in $n$. In this section, we show how to obtain MDAG, where we
still have a bijection between $st$-paths and MCS, but which can instead
always be constructed in $O(n^{3}\sigma\log n)$ time and $O(n^{3}\sigma)$
space, as per Theorem 4.1. Intuitively, the relevant information discussed for
$A$ are the quadruples $(l,m,t,b)$, where $X_{\leq l}$ and $Y_{\leq m}$ are
some prefixes and pair $t,b$ is some swing: these quadruples are the
candidates for being nodes in MDAG.

The formal definition of MDAG is based on an equivalence relation over the
nodes of $A$, given in Section 3.1. Afterwards, in Section 3.2, we describe an
algorithm for directly constructing MDAG. We present the complexity bounds for
the construction in Section 3.3.

###  3.1 Equivalence Relation for Defining MDAG

Let $A$ be a DAG as defined in Definition 2.1. Our construction algorithm for
MDAG is based on the concepts from Section 2.2. The idea is to use the
characterization of valid extensions to identify the out-neighbors of a given
node of DAG $A$. We identify an equivalence relation over the prefixes of
$\mathit{MCS}(X,Y)$, and thus on the nodes of $A$, that allow us to always
build MDAG in polynomial time and space. We begin with the following lemma:

######  Lemma 3.1.

Given any valid prefix $P$, let $X_{\leq l}$ and $Y_{\leq m}$ be the shortest
prefixes containing $P$, and $\ltimes(P)=\langle t,b\rangle$ be its swing.
Consider another valid prefix $P^{\prime}\neq P$ with the _same_ shortest
prefixes $X_{\leq l},Y_{\leq m}$ and swing $\ltimes(P^{\prime})=\ltimes(P)$ as
$P$. Then, the set of valid extensions is the same for both $P$ and
$P^{\prime}$, and for each valid extension $c\in\Sigma$, the swings of $P\,c$
are the same as the ones of $P^{\prime}\,c$.

######  Proof 3.2.

The definition of $\mathit{Ext}_{l,m}$ only depends on the value of $l$ and
$m$, therefore such set is the same for both $P$ and $P^{\prime}$. Since the
swings form $P$ and $P^{\prime}$ are equal, the set of valid extensions is
necessarily the same. Let now $c\in\Sigma$ be a valid extension for $P$ and
$P^{\prime}$. Let $X_{\leq l_{c}}$ and $Y_{\leq m_{c}}$ respectively be the
shortest prefixes of $X$ and $Y$ containing $P\,c$. These are also the
shortest prefixes containing $P^{\prime}\,c$: the shortest prefixes containing
$P$ and $P^{\prime}$ were the same, and $l_{c}$ is simply the first occurrence
of $c$ after $l$, analogously for $m_{c}$ and $m$. The swings of $P\,c$ are
given by the minimum of the swings of $P$, and the personal swing
$\ltimes{(l_{N},m_{N})}$ obtained by adding the new character $c$. The latter
personal swing is the same for both $P\,c$ and $P^{\prime}\,c$, since we are
considering the same positions $l_{c},m_{c}$. Since the previous swings where
also equal, this means that the swings of $P\,c$ and $P^{\prime}\,c$ are
indeed the same.

Lemma 3.1 has an implication for prefixes $P$ and $P^{\prime}$ that share the
same swing: if $M_{1},...,M_{N}$ are strings extending as
$PM_{i}\in\mathit{MCS}(X,Y)$, and $M^{\prime}_{1},...,M^{\prime}_{M}$
extending as $P^{\prime}M^{\prime}_{i}\in\mathit{MCS}(X,Y)$, then they are
equal: $\\{M_{i}\ |\ i=1,...,N\\}=\\{M^{\prime}_{i}\ |\ i=1,...,M\\}$.

Given a node $u$ of $A$, let $P$ be the corresponding prefix. We assign $u$
the quadruple of parameters $\mathit{ID}(u)=\langle
l,m,\ltimes_{T}(P),\ltimes_{B}(P)\rangle$, where $l$ and $m$ are such that
$X_{\leq l}$ and $Y_{\leq m}$ are the shortest prefixes containing $P$. By
Lemma 3.1, this tuple completely identifies the valid extensions of $P$, which
means that it completely identifies the neighbors of node $u$.

######  Corollary 3.3.

Let $u\neq u^{\prime}$ with $\mathit{ID}(u)=\mathit{ID}(u^{\prime})$. Then,
for each $v\in N^{+}(u)$ there exists exactly one $v^{\prime}\in
N^{+}(u^{\prime})$ such that $\mathit{ID}(v)=\mathit{ID}(v^{\prime})$ and
$\ell(u,v)=\ell(u^{\prime},v^{\prime})$.

Therefore, we can define the following _equivalence relation_ on the nodes of
$A$: $u\sim u^{\prime}$ if and only if
$\mathit{ID}(u)=\mathit{ID}(u^{\prime})$. We can then identify a class of
equivalent nodes in the DAG, choosing one representative for it. Because of
Corollary 3.3, this does not change the set of labeled $st$-paths of the DAG:
the nodes that are identified as one have the same labelled out-edges, leading
to the same out-neighbors. Our data structure MDAG is then defined as the DAG
resulting from this identification:

######  Definition 3.4.

Data structure MDAG is a node- and edge-labelled DAG built as follows:

  1. 1.

Start from DAG $A$ (Definition 2.1). For each node $u$, consider its (unique)
corresponding prefix $P$, and let $X_{\leq l}$ and $Y_{\leq m}$ be the
shortest prefixes of $X$ and $Y$ containing $P$, and $\ltimes(P)=(t,b)$.
Assign to node $u$ the node-label $\mathit{ID}(u)=\langle l,m,t,b\rangle$.

  2. 2.

Merge every pair of nodes $u\neq u^{\prime}$ with the same label
$\mathit{ID}(u)=\mathit{ID}(u^{\prime})$ into one node.

An example of such DAG is shown in the right of Figure 1.

The compact MDAG is the version with compressed _unary paths_. Each such path
$u_{1}...u_{k}$ has $N^{+}(u_{i})=\\{u_{i+1}\\}$ for each $i$, and is replaced
by the single edge $(u_{1},u_{k})$, with label
$\ell(u_{1},u_{k})=\ell(u_{1},u_{2})\ell(u_{2},u_{3})...\ell(u_{k-1},u_{k})$.
Note that compressing unary paths does not change the set of labeled
$st$-paths of the DAG, which still correspond to $\mathit{MCS}(X,Y)$.

###  3.2 Direct and Incremental Construction of MDAG

We build MDAG directly, without the intermediate DAG $A$, We apply the
incremental procedure below, in a DFS fashion, using the node $ID$s to avoid
repeated computation. At any moment we have built a node- and edge-labeled DAG
$H=(W,F)$. A node $u\in W$ corresponds to a set of prefixes $P_{1},...,P_{k}$,
given by the concatenation of the edge-labels of all $su$-paths using edges of
$F$. All prefixes $P_{i}$ share the same ending positions of the shortest
prefixes of $X$ and $Y$ that contain them, and the corresponding swings; these
four values form the label $\mathit{ID}(u)$ assigned to $u$.

Every recursive call $\textsc{buildDAG}(u)$ takes as input a node $u$ which
belongs to the current DAG $H$, and expands DAG $H$ accordingly as follows:

  1. 1.

Let $\mathit{ID}(u)=\langle l,m,t,b\rangle$. First, compute set
$\mathit{Ext}_{l,m}$, and use it to compute the valid extensions: select
characters $c$ that have a corresponding pair $(i,j)\in\mathit{Ext}_{l,m}$,
with $i\leq t$ and $j\leq b$.

  2. 2.

For such character $c$, compute the positions $(l_{c},m_{c})$ such that
$X_{\leq l_{c}}$ and $Y_{\leq m_{c}}$ are the shortest prefixes containing
$P\,c$, and update the swings $t_{c},b_{c}$.

  3. 3.

Now, check if the DAG $H$ generated so far already has a node with label
$\langle l_{c},m_{c},t_{c},b_{c}\rangle$:

    1. (a)

If such a node $v\in W$ exists, then simply add edge $(u,v)$ with label $c$ to
the edges $F$ of $H$, without recursing. Indeed, a recursive call for $v$ has
been previously performed.

    2. (b)

Otherwise, add node $v$ to $W$, with $\mathit{ID}(v)=\langle
l_{c},m_{c},t_{c},b_{c}\rangle$, and add edge $(u,v)$ to $F$, with label $c$.
Then, perform the recursive call $\textsc{buildDAG}(v)$.

######  Corollary 3.5 (Correctness).

$\textsc{buildDAG}(s)$ correctly builds $\textsf{MDAG}(X,Y)$ starting from
$H=(\\{s\\},\emptyset)$.

######  Proof 3.6.

We show that, at every step, $H$ is a subgraph of DAG $A$ where nodes with
equal $\mathit{ID}()$ values have been identified. This is true at the
beginning, when $H=\\{s\\}$. If this holds at the beginning of a recursive
call for a node $u$, then it must hold at the end. Indeed, we use valid
extensions to identify neighbors of a given node, which is also the definition
of neighbors for a node of $A$. For each valid extension $c$, we compute the
label $\langle l_{c},m_{c},t_{c},b_{c}\rangle$ of the corresponding node. Now,
if there already exists a node $v$ with such label, we add an edge between $u$
and $v$. This correctly identifies the two nodes with equal labels as being
the same node, as per operation 2. Otherwise, the new node must be added, with
the correct label $\langle l_{c},m_{c},t_{c},b_{c}\rangle$ as per operation 1,
since it represents a new prefix.

Once we have built MDAG, we can easily compute compact MDAG in linear time in
the size of MDAG, in the following way. Let us proceed in topological order of
the nodes; when a node $v$ with $N^{+}(v)=\\{w\\}$ (i.e. out-degree 1) is
encountered, we perform the following:

  1. 1.

For each $u\in N^{-}(v)$, remove edge $(u,v)$ and add edge $(u,w)$ with label
$\ell(u,v)\ell(v,w)$.

  2. 2.

After all in-neighbors have been processed, remove node $v$ and edge $(v,w)$
from MDAG.

Clearly, the minimum out-degree of is 2, and nodes $s$ and $t$ are never
removed.

Complexity. Let us now study the time and space complexity of the procedure.
As mentioned before, finding $\mathit{Ext}_{l,m}$ requires $O(\sigma\log n)$
time (see [5] for details). Checking whether each $c$ corresponding to an
element of $\mathit{Ext}_{l,m}$ satisfies the swings’ condition requires
constant time per character. For each such $c$, computing positions
$(l_{c},m_{c})$ can be done in constant time, while updating the swings
accordingly can be performed in $O(\sigma)$ time, provided appropriate data
structures. Indeed, to ensure this we only need to ensure constant-time
queries for the next occurrence of character $c$ after a given position $i$.
To this end, let us keep two bit-vectors for each $c\in\Sigma$, one for $X$
and one for $Y$, indicating the positions in which $c$ occurs in the strings.
By equipping these vectors with rank and select data structures, which employ
$O(n\sigma)$ space, we can find in constant time the next occurrence of any
character after a given position [17]. All operations described so far are
performed exactly once per node. Therefore, the total time required for these
is $O(|V|\sigma\log n)$.

Let us now consider Step 3. We need to check if a node $v$ belongs to the
current DAG, and add it if it does not. To be able to efficiently perform
these operations, let us keep and dynamically update a bit matrix for pairs
$l$, $m$, where 1 occurs if that pair currently corresponds to at least one
node. Then, each cell filled with a one has an associated balanced binary
search tree, which indexes the pairs of swings $(t,b)$ such that there
currently is a node $u\in W$ with $\mathit{ID}(u)=\langle l,m,t,b\rangle$.
These pairs are ordered according to the total order:
$(t,b)<(t^{\prime},b^{\prime})$ if and only if $t<t^{\prime}$ or
$t=t^{\prime}$ and $b<b^{\prime}$. Lookup and insertions in such data
structure require $O(\log n)$ each, and the total space employed is $O(|V|)$.
Now, note that we perform a membership check, with subsequent possible
insertion, exactly once per edge of the DAG. Recalling that
$|E|\leq\sigma|V|$, the total time required by these operations is again
$O(|E|\log n)=O(|V|\sigma\log n)$.

To be able to give final complexity bounds, we therefore need bounds on the
size of the DAG we constructed. Trivially, we can bound $|V|=O(n^{4})$, since
no two nodes share the same $ID$, and the number of different $ID$s is bounded
by $n^{4}$. Therefore, we surely have a polynomial-time and space algorithm
for building a DAG. We can actually do better than this: thanks to some
properties of the swings, in the next section we show that $|V|=O(n^{3})$,
leading to the complexity bounds given in Theorem 4.1.

###  3.3 Cubic Size of the MCS DAG

To conclude the proof of Theorem 4.1, we need to study the size of
$\textsf{MDAG}(X,Y)$ as constructed in Section 3.2. We prove a monotonicity
property of the swing values, which will allow us to show that the number of
nodes of $\textsf{MDAG}(X,Y)$ is bounded by $O(n^{3})$.

In Section 2.2, we saw that the top swing of a prefix $P$ is defined as
$\ltimes_{T}(P)=\min\\{i>l\ |\ P\not\in\mathit{MCS}(X_{\leq i},Y_{\leq
m})\\}$, where $X_{\leq l}$ and $Y_{\leq m}$ are the shortest prefixes of
respectively $X$ and $Y$ containing $P$. In other words, if we start from
strings $X_{\leq l},Y_{\leq m}$ (where $P$ is obviously maximal), it is the
minimum extension of string $X$ that ensures at least one insertion in $P$.
Symmetrical definition holds for bottom swings, by switching the two strings.

Note that, if $\ltimes_{T}(P)=t$, then $X[t]=Y[m]=X[l]$: the swings’ positions
are occurrences of the last character of the prefix. Indeed, the swing is the
first occurrence of character $Y[m]=X[l]$, after certain positions in string
$X$ (see the incremental computation of swings in Section 2.2). We also note
the following, which follows from the definition of swings:

######  Remark 3.7.

Let $P=p_{1}\cdots p_{N}$ a valid prefix with swings $\langle t,b\rangle$. Let
$X_{\leq l_{i}}$ and $Y_{\leq m_{i}}$ be the shortest prefixes respectively of
$X$ and $Y$ that contain $p_{1}\cdots p_{i}$. Then, there is at least one
match between $Y[m_{N-1},m_{N})$ and $X(l_{N},t)$. More specifically, there
can either be a match between $Y(m_{N-1},m_{N})$ and $X(l_{N},t)$, or between
$Y[m_{N-1}]$ and $X(l,t)$ which will lead to an insertion in a previous part
of the prefix.

We briefly also recall how to incrementally compute the swings of a prefix,
first described in [5], as it will be useful in our proofs. We only describe
the procedure for the top swing as the bottom swing is symmetrical:

  * •

If $P$ is composed of a single character $c$, with first occurrence in $X$ at
position $l$ and in $Y$ at position $m$, then it suffices to compute, for
every character $d$ in $Y_{<m}$, the first occurrence of $d$ in $X_{>l}$, and
take the minimum of these. The swing then corresponds to the first occurrence
of $c$ after such minimum.

  * •

Let $P=p_{1}\cdots p_{N}$ be a valid prefix with $N>1$, and let
$l_{1},...,l_{N}$ (resp. $m_{1},...,m_{N}$) be the positions of $X$ (resp.
$Y$) such that $X_{\leq l_{i}}$ (resp. $Y_{\leq m_{i}}$) is the shortest
prefix containing $p_{1}\cdots p_{i}$. The _personal swing_
$\ltimes_{T}{(l_{N},m_{N})}$ of the last position is the swing of character
$p_{N}$ when seen as a prefix over the strings $X_{>l_{N-1}},Y_{>m_{N-1}}$,
instead of over the whole strings (and thus computed as above). In other
words, the personal swing of a character expresses the change necessary to
have an insertion between itself and the previous character of the prefix. The
top swing of $P$ is the minimum between the personal swing of $(l_{N},m_{N})$,
and the first occurrence of $Y[m_{N}]=p_{N}$ after the top swing of prefix
$p_{1}\cdots p_{N-1}$. This second swing indicates the change required for an
insertion in the previous part of the prefix.

We now present some new swing properties. This lemma proves that, when two
prefixes are extended with a valid extension that occurs at the same pair of
positions, then the relative order of the swings remains unchanged during the
extension:

######  Lemma 3.8.

Let $u$ and $u^{\prime}$ be two nodes of MDAG, with $\mathit{ID}(u)=\langle
x,y,\ltimes_{T}(P),\ltimes_{B}(P)\rangle$ and $\mathit{ID}(u^{\prime})=\langle
x^{\prime},y^{\prime},\ltimes_{T}(P^{\prime}),\ltimes_{B}(P^{\prime})\rangle$
such that $x\neq x^{\prime}$ or $y\neq y^{\prime}$, where $P$ (resp.
$P^{\prime}$) is any prefix associated to $u$ (resp. $u^{\prime}$). Assume
that we have $v\in N^{+}(u)$ with $\mathit{ID}(v)=\langle
l,m,\ltimes_{T}(P\,c),\ltimes_{B}(P\,c)\rangle$, and $v^{\prime}\in
N^{+}(u^{\prime})$ with $\mathit{ID}(v^{\prime})=\langle
l,m,\ltimes_{T}(P^{\prime}\,c),\ltimes_{B}(P^{\prime}\,c)\rangle$ (i.e. same
positions $l,m$ corresponding to character $c$). Then, the swings change
monotonically:

  * •

$\ltimes_{T}(P)<\ltimes_{T}(P^{\prime})\Rightarrow\ltimes_{T}(P\,c)\leq\ltimes_{T}(P^{\prime}\,c)$

  * •

$\ltimes_{B}(P)<\ltimes_{B}(P^{\prime})\Rightarrow\ltimes_{B}(P\,c)\leq\ltimes_{B}(P^{\prime}\,c)$

######  Proof 3.9.

We prove the result for top swings. Let $\ltimes_{T}(P)=t$ and
$\ltimes_{T}(P^{\prime})=t^{\prime}$, with $t<t^{\prime}$. We note that for
$(l,m)$ to be a valid extension for both prefixes, we must have $l\leq
t<t^{\prime}$ (Swing condition 1 for valid extensions’ characterization in
Section 2.2). By the incremental computation of swings, the swings of $P\,c$
and $P^{\prime}\,c$ are computed by taking the minimum between the personal
swing $\ltimes_{T}^{(l,m)}$ of the new positions, and the next occurrence of
the corresponding character after the top swings $t,t^{\prime}$. More
specifically,
$\ltimes_{T}(P\,c)=\min\\{\ltimes_{T}^{(l,m)},\mathit{next}_{X}(c,t)\\}$ and
$\ltimes_{T}(P^{\prime}\,c)=\min\\{\ltimes_{T}^{(l,m)},\mathit{next}_{X}(c,t^{\prime})\\}$.
Since the first component of the minimum is the same, it suffices to prove
that $\mathit{next}_{X}(c,t)\leq\mathit{next}_{X}(c,t^{\prime})$ to conclude
$\ltimes_{T}(P\,c)\leq\ltimes_{T}(P^{\prime}\,c)$. Indeed, since
$t<t^{\prime}$ are positions in the same string, the next occurrence of a
given character after $t$ cannot be strictly bigger than the next occurrence
of the same character after $t^{\prime}$. Thus, we have proved the claim for
top swings; bottom swings are symmetrical.

The next corollary shows that the opposite implication holds for strict
inequalities:

######  Corollary 3.10.

Under the same hypotheses of Lemma 3.8, we have

  * •

$\ltimes_{T}(P\,c)<\ltimes_{T}(P^{\prime}\,c)\Rightarrow\ltimes_{T}(P)<\ltimes_{T}(P^{\prime})$

  * •

$\ltimes_{B}(P\,c)<\ltimes_{B}(P^{\prime}\,c))\Rightarrow\ltimes_{B}(P)<\ltimes_{B}(P^{\prime})$

######  Proof 3.11.

We reverse the proof of Lemma 3.8. Consider top swings, and recall
$\ltimes_{T}(P\,c)=\min\\{\ltimes_{T}^{(l,m)},\mathit{next}_{X}(c,t)\\}$ and
$\ltimes_{T}(P^{\prime}\,c)=\min\\{\ltimes_{T}^{(l,m)},\mathit{next}_{X}(c,t^{\prime})\\}$,
where $t=\ltimes_{T}(P)$ and $t^{\prime}=\ltimes_{T}(P^{\prime})$. Since the
first part of the minimum is the same, and
$\ltimes_{T}(P\,c)<\ltimes_{T}(P^{\prime}\,c)$, we have two options

  1. 1.

$\mathit{next}_{X}(c,t)\leq\ltimes_{T}^{(l,m)}\leq\mathit{next}_{X}(c,t^{\prime})$,
where at most one inequality can be an equality; or

  2. 2.

$\mathit{next}_{X}(c,t)<\mathit{next}_{X}(c,t^{\prime})\leq\ltimes_{T}^{(l,m)}$.

In any case, we have $\mathit{next}_{X}(c,t)<\mathit{next}_{X}(c,t^{\prime})$.
Since $t$ and $t^{\prime}$ are positions in the same string, this relationship
between the next occurrence of the same character immediately also implies
$t<t^{\prime}$, which concludes the proof.

We are now ready to prove our main result:

######  Theorem 3.12.

For any two nodes $u\neq u^{\prime}$ of MDAG, let $\mathit{ID}(u)=\langle
l,m,t,b\rangle$ and $\mathit{ID}(u^{\prime})=\langle
l,m,t^{\prime},b^{\prime}\rangle$. Then swing pairs for the same $l,m$ do not
dominate each other; namely, if $t>t^{\prime}$, then $b\leq b^{\prime}$.

######  Proof 3.13.

Consider any $v\in N^{-}(u)$, and $v^{\prime}\in N^{-}(u^{\prime})$. Let
$\mathit{ID}(v)=\langle x,y,t_{v},b_{v}\rangle$ and
$\mathit{ID}(v^{\prime})=\langle
x^{\prime},y^{\prime},t_{v^{\prime}},b_{v^{\prime}}\rangle$. Let us first
assume that $x\neq x^{\prime}$ or $y\neq y^{\prime}$, i.e. they are not the
same pair of positions. If we look at positions $(x,y)$ and
$(x^{\prime},y^{\prime})$ we must have either $x\leq x^{\prime}$ and
$y>y^{\prime}$, or $x>x^{\prime}$ and $y\leq y^{\prime}$. Indeed, assume by
contradiction that $x\leq x^{\prime}$ and $y\leq y^{\prime}$. Since both of
these nodes have a valid extension corresponding to positions $(l,m)$, we must
also have $x\leq x^{\prime}<l<t_{v},t_{v^{\prime}}$ and $y\leq
y^{\prime}<m<b_{v},b_{v^{\prime}}$. Then, $(l,m)$ would not be a valid
extension for $v$: the corresponding prefix is not maximal until the positions
given by the swings, since we have an insertion corresponding to the character
occurring at positions $(x^{\prime},y^{\prime})$.

We now show that $t>t^{\prime}$ implies $y>y^{\prime}$. By Remark 3.7, $t$ is
the smallest value such that a match occurs between $X[l+1,t)$ and $Y[y,m-1]$.
That is, there is no $\tau<t$ such that $X[l+1,\tau)$ and $Y[y,m-1]$ have a
match. Let $t>t^{\prime}$, and assume by contradiction that $y\leq
y^{\prime}$. Then, $Y[y^{\prime},m-1]\subseteq Y[y,m-1]$. By definition of
$t^{\prime}$, there is a match between $X[l+1,t^{\prime})$ and
$Y[y^{\prime},m-1]\subseteq Y[y,m-1]$. This is a contradiction on the
minimality of $t$: there is a smaller $\tau=t^{\prime}<t$ which yields a
match. Now, since we cannot have both $y^{\prime}\leq y$ and $x^{\prime}\leq
x$, we must have $x\leq x^{\prime}$. By a symmetrical reasoning, we show that
the bottom swings must satisfy $b^{\prime}\leq b$. Indeed, recall that $b$ is
the minimum value for which a match occurs between $X[x,l-1]$ and $Y[m+1,b]$,
and assume by contradiction that $b>b^{\prime}$. Since we have
$X[x^{\prime},l-1]\subseteq X[x,l-1]$, we have a match between $X[x,l-1]$ and
$Y[m+1,b^{\prime}]$ for a smaller value $b^{\prime}<b$: contradiction.

Let us now consider the case where the in-neighbors $v$ and $v^{\prime}$ have
the same pair of positions in their $ID$s: $x=x^{\prime}$ and $y=y^{\prime}$.
Let us inductively consider $w_{i+1}\in N^{-}(w_{i})$ and $w_{i+1}^{\prime}\in
N^{-}(w_{i}^{\prime})$, where $w_{0}=v$ and $w^{\prime}_{0}=v^{\prime}$. We
stop at the first $j$ such that $\mathit{ID}(w_{j})=\langle
x_{j},y_{j},t_{j},b_{j}\rangle$ and $\mathit{ID}(w^{\prime})=\langle
x^{\prime}_{j},y^{\prime}_{j},t^{\prime}_{j},b^{\prime}_{j}\rangle$ with
$x_{j}\neq x^{\prime}_{j}$ or $y_{j}\neq y^{\prime}_{j}$. Such pair satisfies
the conditions of the first part of the proof, since
$x_{j+1}=x^{\prime}_{j+1}$ and $y_{j+1}=y^{\prime}_{j+1}$ by hypothesis. Nodes
$w_{j}$ and $w_{j}^{\prime}$ are obtained by going backwards in the DAG for
$j$ steps, starting respectively from nodes $u$ and $u^{\prime}$. Since $j$ is
the first index such that the corresponding positions for extensions differ,
we have $\ell(w_{k+1},w_{k})=\ell(w^{\prime}_{k+1},w^{\prime}_{k})$ for all
$k=1,...,j-1$. By iterating Corollary 3.10, we thus have that $t>t^{\prime}$
implies $t_{j}>t_{j}^{\prime}$. By the first part of the proof, we therefore
have $b_{j}\leq b_{j}^{\prime}$. By Lemma 3.8, this propagates to the end of
the path in the MCS DAG, to also yield $b\leq b^{\prime}$.

From Theorem 3.12, we can derive the following result, which proves that the
number of swings for a fixed pair of positions $(l,m)$ is linear:

######  Corollary 3.14.

For any given choice of $l,m$, there are just $O(n)$ nodes of
$\textsf{MDAG}(X,Y)$ having the form $\mathit{ID}()=\langle
l,m,\cdot,\cdot\rangle$.

######  Proof 3.15.

Let us fix $l,m$, and consider the set
$S_{l,m}\subseteq\\{0,...,n-1\\}\times\\{0,...,n-1\\}$, where $(a,b)\in
S_{l,m}$ if and only there exists $u$ such that $\mathit{ID}(u)=\langle
l,m,a,b\rangle$. By Theorem 3.12, if two pairs $(a,b)$ and $(c,d)$ belong to
$S_{l,m}$, then it cannot be $a\leq c$ and $c\leq d$ (or vice versa). So one
pair cannot dominate the other.

We observe that the size of $|S_{l,m}|$ is the size of the classical Pareto
frontier: for an arbitrary set of points in the
$\\{0,...,n-1\\}\times\\{0,...,n-1\\}$ grid, the number of points in a Pareto
frontier is less than $2n$. The observation is folklore: each point in the
frontier either increases the $x$-coordinate or decreases the $y$-coordinate
(possibly both). Hence, there cannot be more points on the frontiers as the
sum of the $n$ possible $x$-coordinates plus the $n$ possible $y$-coordinates.
Hence, $|S_{l,m}|=O(n)$.

Therefore, the number of nodes of the MCS DAG is cubic, as we have $O(n^{2})$
choices for $l,m$, and every such choice gives at most a linear amount of
swings $(t,b)$. Furthermore, it is immediate by construction of MDAG that the
out-degree of every node is at most $\sigma$ (the characters that are valid
extensions the given prefix). Therefore, we proved the space occupancy of
$O(n^{3}\sigma)$ memory words stated in Theorem 4.1.

##  4 Efficient Operations on MDAG

We describe here how to support some operations on compact
$\textsf{MDAG}(X,Y)$, which has source $s$, target $t$, and no unary nodes. We
assume that each node $u$ stores the number $p(u)$ of $ut$-paths. As compact
$\textsf{MDAG}(X,Y)$ is a DAG of $O(n^{3}\sigma)$ edges, we can computed
$p(u)$ for each node $u$ in total $O(n^{3}\sigma)$ time by running a DFS, as
$p(u)$ is the sum of the $p(v)$’s for the out-neighbors $v$’s of $u$.

###  4.1 CAT Enumeration of MCSs

The strings in $\mathit{MCS}(X,Y)$ can be listed in lexicographic order by
enumerating the (labeled) $st$-paths in compact MDAG, which can be done in
Constant Amortized Time with a simple DFS algorithm where the out-neighbors of
each node are visited in increasing order of the labels of their outgoing
edges. Although folklore, for completeness we sketch the DFS algorithm here.

Consider a node $u$, where initially $u=s$, and denote the set of all
$ut$-paths in $G=$ compact $\textsf{MDAG}(X,Y)$ by $\mathcal{P}_{u,t}(G)$. The
central idea is that any $ut$-path starts with $u$, followed by an element of
$\mathcal{P}_{v,t}(G\setminus u)$, i.e., a path in $G\setminus u$ (i.e. $u$
and its incident edges removed) from an out-neighbor $v$ of $u$ to $t$. Since
$G$ is a DAG, we can go a step further: a path from $u$ cannot reach $u$
again, therefore it is not even necessary to remove $u$ (and its incident
edges) from the DAG. We can thus represent $\mathcal{P}_{u,t}(G)$ as the
following disjoint union: $\mathcal{P}_{u,t}(G)=\bigcup_{v\in
N(u)}\\{\ell(u,v)P\mid P\in\mathcal{P}_{v,t}(G)\\}.$ From this, it is
immediate that enumeration can be performed by keeping a current path prefix
which we expand by traversing the DAG, backtracking every time computation
terminates for all children of a node.

To obtain constant amortized time from this, we only need three simple
observations:

  * •

Every path leads to $t$, so each branch of the computation leads to a leaf of
the recursion tree representing a solution.

  * •

Each node except $t$ has at least $2$ out-neighbors due to the path
compression in $G$, so the recursion tree generated has no unary nodes,
meaning the number of internal recursion-nodes is not greater than the leaves
(solutions).

  * •

In each recursive node we spend just constant time per recursive child, so the
total time is $O(N)$, where $N$ is the number of solutions.

###  4.2 Searching, Selecting, and Ranking

We observe that each node $u$ has at most $\sigma$ out-neighbors and the edges
towards them are distinct (each must start with a different character of
$\Sigma$): this constitutes a “lexicographical partition” of the paths from
$u$ to $t$ since, after a common prefix, a path starting with a larger
character will lead to a lexicographically larger string.

Searching a string $P$ as a prefix of strings from $\mathit{MCS}(X,Y)$
traverses compact MDAG starting from $s$ and matching the characters in $P$
along the labels for the edges in the path. Either the search fails before
reaching the end of $P$, or it succeeds and leads to a node $u$. At this
point, we can run the CAT enumeration (Section 4.1) starting from $u$ to list
all the $ut$-paths and so all the extensions of $P$ to strings in
$\mathit{MCS}(X,Y)$.

Selecting the $i$th string in lexicographic order from $\mathit{MCS}(X,Y)$ is
similar but uses the information $p(v)$ in each traversed node $v$. It scans
the outgoing edges in order of their labels, and checks the corresponding
$p(v)$: whenever the edges scanned have the smallest partial sum $\geq i$, it
follows the current edge and subtracts from $i$ this partial sum. It stops at
node $t$. Let $S$ be the string thus found by concatenating the labels on the
traced path from $s$ to $t$. The number of traversed nodes is at most $|S|+1$,
and in each node we will consider up to $\sigma$ edges, for a total cost of
$O(|S|\log\sigma)$, as this can be further optimized by storing, for each
edge, the sum of the annotations of the previous edges, and using binary
search on these $O(\sigma)$ sums. Ranking $S$ is like searching $S$ and using
the partial sums as mentioned above to get a total sum of $i$ when $t$ is
reached.

######  Theorem 4.1.

Given two strings $X$ and $Y$ of length $n$ on an alphabet of size $\sigma$,
compact $\textsf{MDAG}(X,Y)$ stores $\mathit{MCS}(X,Y)$ in space
$O(n^{3}\sigma)$ and can be built in $O(n^{3}\sigma\log n)$ time. It supports
the following operations:

  * •

For a given string $P$, report all the strings with prefix $P$ from
$\mathit{MCS}(X,Y)$ in $O(|P|\log\sigma+\mathit{occ})$ time, where
$\mathit{occ}$ is the number of reported strings.

  * •

For any integer $1\leq i\leq|\mathit{MCS}(X,Y)|$, select the $i$th string $S$
in lexicographic order from $\mathit{MCS}(X,Y)$, in $O(|S|\log\sigma)$ time.

  * •

For any string $S\in\mathit{MCS}(X,Y)$, return its rank $i$ among the strings
in lexicographic order from $\mathit{MCS}(X,Y)$, in $O(|S|\log\sigma)$ time.

  * •

List all strings in $\mathit{MCS}(X,Y)$ in $O(|\mathit{MCS}(X,Y)|)$ time,
i.e., Constant Amortized Time.

It is worth noting that (compact) MDAG can be stored in a succinct way, for
example, using some recent methods introduced for automata [4].

##  5 Conclusions

In this paper we considered the problem of storing and searching the Maximal
Common Subsequences of two input strings, as they may reveal further common
structures in sequence analysis with respect to the LCSs. Our main
contribution is that of reducing time and space from exponential bounds, using
the current state of the art, to polynomial bounds, using our new compact DAG,
which supports CAT enumeration, counting, and random access to the $i$-th
element (i.e., rank and select operations) in nearly optimal time.

## References

  * [1] A. Abboud, A. Backurs, and V. V. Williams.  Tight hardness results for LCS and other sequence similarity measures.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 59–78, Oct 2015.  doi:10.1109/FOCS.2015.14.
  * [2] Ricardo A Baeza-Yates.  Searching subsequences.  Theoretical Computer Science, 78(2):363–376, 1991.
  * [3] L. Bergroth, H. Hakonen, and T. Raita.  A survey of longest common subsequence algorithms.  In Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000, pages 39–48, Sep. 2000.  doi:10.1109/SPIRE.2000.878178.
  * [4] Sankardeep Chakraborty, Roberto Grossi, Kunihiko Sadakane, and Srinivasa Rao Satti.  Succinct representation for (non)deterministic finite automata.  J. Comput. Syst. Sci., 131:1–12, 2023.  doi:10.1016/j.jcss.2022.07.002.
  * [5] Alessio Conte, Roberto Grossi, Giulia Punzi, and Takeaki Uno.  Enumeration of maximal common subsequences between two strings.  Algorithmica, pages 1–27, 2022.
  * [6] Maxime Crochemore, Bořivoj Melichar, and Zdeněk Troníček.  Directed acyclic subsequence graph—overview.  Journal of Discrete Algorithms, 1(3-4):255–280, 2003.
  * [7] Maxime Crochemore and Zdeněk Troníček.  Directed acyclic subsequence graph for multiple texts.  Rapport IGM, pages 99–13, 1999.
  * [8] C. B. Fraser, R. W. Irving, and M. Middendorf.  Maximal common subsequences and minimal common supersequences.  Information and Computation, 124(2):145 – 153, 1996.  URL: http://www.sciencedirect.com/science/article/pii/S0890540196900115, doi:https://doi.org/10.1006/inco.1996.0011.
  * [9] Miyuji Hirota and Yoshifumi Sakai.  A fast algorithm for finding a maximal common subsequence of multiple strings.  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, page 2022DML0002, 2023.
  * [10] D. S. Hirschberg.  Algorithms for the longest common subsequence problem.  J. ACM, 24(4):664–675, October 1977.  URL: http://doi.acm.org/10.1145/322033.322044, doi:10.1145/322033.322044.
  * [11] W. J. Hsu and M. W. Du.  Computing a longest common subsequence for a set of strings.  BIT Numerical Mathematics, 24(1):45–59, 1984.
  * [12] Elsa Loekito, James Bailey, and Jian Pei.  A binary decision diagram based approach for mining frequent subsequences.  Knowl. Inf. Syst., 24(2):235–268, 2010.  URL: https://doi.org/10.1007/s10115-009-0252-9, doi:10.1007/s10115-009-0252-9.
  * [13] David Maier.  The complexity of some problems on subsequences and supersequences.  Journal of the ACM (JACM), 25(2):322–336, 1978.
  * [14] W. J. Masek and M. S. Paterson.  A faster algorithm computing string edit distances.  Journal of Computer and System Sciences, 20(1):18 – 31, 1980.  URL: http://www.sciencedirect.com/science/article/pii/0022000080900021, doi:https://doi.org/10.1016/0022-0000(80)90002-1.
  * [15] Bořivoj Melichar and Tomáš Polcar.  The longest common subsequence problem a finite automata approach.  In Implementation and Application of Automata: 8th International Conference, CIAA 2003 Santa Barbara, CA, USA, July 16–18, 2003 Proceedings, pages 294–296. Springer, 2003.
  * [16] Shin-ichi Minato.  Zero-suppressed bdds for set manipulation in combinatorial problems.  In Proceedings of the 30th International Design Automation Conference, DAC ’93, page 272–277, New York, NY, USA, 1993. Association for Computing Machinery.  URL: https://doi.org/10.1145/157485.164890, doi:10.1145/157485.164890.
  * [17] R. Raman, V. Raman, and S. R. Satti.  Succinct indexable dictionaries with applications to encoding $k$-ary trees, prefix sums and multisets.  ACM Trans. Algorithms, 3(4):43–es, November 2007.  URL: https://doi.org/10.1145/1290672.1290680, doi:10.1145/1290672.1290680.
  * [18] Frank Ruskey.  Combinatorial generation.  Preliminary working draft. University of Victoria, Victoria, BC, Canada, 11:20, 2003.
  * [19] Yoshifumi Sakai.  Maximal common subsequence algorithms.  In Gonzalo Navarro, David Sankoff, and Binhai Zhu, editors, Annual Symposium on Combinatorial Pattern Matching (CPM 2018), volume 105 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:10, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2018/8707, doi:10.4230/LIPIcs.CPM.2018.1.
  * [20] Yoshifumi Sakai.  Maximal common subsequence algorithms.  Theoretical Computer Science, 793:132–139, 2019.  URL: https://www.sciencedirect.com/science/article/pii/S0304397519304074, doi:https://doi.org/10.1016/j.tcs.2019.06.020.
  * [21] Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi.  The worst-case time complexity for generating all maximal cliques and computational experiments.  Theoretical Computer Science, 363(1):28–42, 2006.  Computing and Combinatorics.
  * [22] Zdeněk Troníček.  Common subsequence automaton.  In International Conference on Implementation and Application of Automata, pages 270–275. Springer, 2002.
  * [23] R. A. Wagner and M. J. Fischer.  The string-to-string correction problem.  J. ACM, 21(1):168–173, January 1974.  URL: http://doi.acm.org/10.1145/321796.321811, doi:10.1145/321796.321811.