如果存在包含子序列 A 和 B 但不包含 F 的字符串的算法

Question

我正在为以下问题寻找有效的算法：

我们得到三个字符串 A、B 和 F 作为输入，我们需要判断是否存在字符串 X，使得 A 和 B 是 X 的子序列，但 F 不是。算法的输出应该是 "Yes" 或 "No"。

字符串的子序列是可以通过从原始字符串中删除一些字母而不改变其余字母的顺序来创建的任何字符串。

例如，如果A = "aabab"，B = "bbaa"，F = "baba"，算法应该输出"Yes"，因为"aabbaab"有A和 B 作为子序列而不是 F.

有什么想法吗？

Answer 1

设 X 是 A 和 B 的最小超序列 如果 X 的每个字母都可以匹配到 A and/or B顺序。

A 和 B 的每个超序列都是 F 的超序列当且仅当A 和 B 的每个最小超序列都是 F.

的超序列

接受 A 和 B 的最小超序列的 DFA 最多可以轻松构建 |A| *|B| 个状态，每个状态对应两个字符串中的一对兼容位置。参见 https://en.wikipedia.org/wiki/Deterministic_finite_automaton and https://en.wikipedia.org/wiki/Powerset_construction

如果A和B的超序列不是F[=59=的超序列]，则存在一条通过此 DFA 的路径不是 F.

的超序列
将通过 DFA 的路径的成本定义为 F 的最长前缀的长度，该前缀是路径的子序列，即您要匹配的字符数从 F 沿着路径。

然后，由于 DFA 是非循环的，您可以使用 Dijkstra 算法或最佳优先搜索来找到到达每个状态的最低成本。参见 https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

如果任何接受状态的最小成本小于 |F|，则存在 A 和 B 也不是 F.
的超序列
整个操作的复杂度是O(|A|*|B|)

最简单的实现方式是使用 |A|+1 x |B|+1 矩阵作为 DFA -- 就像您用于 LCS 计算的那个一样。矩阵中的每个单元格都是一个状态。发现单元格时用最少的成本填充单元格。

Answer 2

既然我对这个问题有了更多的思考，我找到了一个非常简单有效的解决方案。 ;) 这个问题真的比我最初想象的要容易得多。它可以在线性 O(|A| + |B|) 时间内解决，无需任何额外的 space。

想法是遍历 F 的字符，并始终将 A 和 B 的最大部分取到超序列中，以便不超过 F 的当前前缀是它的子序列。下面的 C++ 代码阐明了这个想法：

int i = 0, j = 0;
for (int k = 0; k < F.size()-1; k++) {
    while (i < A.size() && A[i] != F[k]) i++;
    while (j < B.size() && B[j] != F[k]) j++;
    i++; j++;
    if (i >= A.size() && j >= B.size()) {
        cout << "YES";
        return 0;
    }
}
cout << "NO";

如果存在包含子序列 A 和 B 但不包含 F 的字符串的算法

Algorithm if there is a string including subsequences A and B but not F

algorithm

subsequence