  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.
