A Maximal Common Subsequence (MCS) between two strings X and Y is an inclusion-maximal subsequence of both X and Y. MCSs are a natural generalization of the classical concept of Longest Common Subsequence (LCS), which can be seen as a longest MCS. We study the problem of efficiently listing all the distinct MCSs between two strings. As discussed in the paper, this problem is algorithmically challenging as the same MCS cannot be listed multiple times: for example, dynamic programming [Eraser et al., CPM 1998] incurs in an exponential waste of time, and a recent algorithm for finding an MCS [Sakai, CPM 2018] does not seem to immediately extend to listing. We follow an alternative and novel graph-based approach, proposing the first output-sensitive algorithm for this problem: it takes polynomial time in n per MCS found, where n = max{|X|, |Y|}, with polynomial preprocessing time and space.
展开▼
机译：两个字符串X和Y之间的最大公共子序列（MCS）是X和Y的包含最大子序列。MCS是经典概念最长公共子序列（LCS）的自然概括，可以视为最长MCS 。我们研究了有效列出两个字符串之间所有不同的MCS的问题。正如本文所讨论的那样，该问题在算法上具有挑战性，因为同一MCS不能多次列出：例如，动态编程[Eraser等人，CPM 1998]导致时间成倍的浪费，而最近的算法却发现了MCS [Sakai，CPM 2018]似乎没有立即扩展到上市。我们采用另一种基于图的新颖方法，针对此问题提出了第一种输出敏感算法：每个发现的MCS花费n的多项式时间，其中n = max {| X |，| Y |}，并具有多项式预处理时间和空间。
展开▼
