算法，如果有一个字符串，包括子序列 A 和 B，但不包括 F

Question

我正在寻找一个有效的算法来解决以下问题：

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

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

例如，如果 A = "aabab"，B = ">

bbaa"，F = "baba"，则算法应输出"Yes"，因为 "aabbaab" 将 A 和 B 作为子序列，而不是 F。

有什么想法吗？

Answer 1

如果X的每个字母都可以按顺序匹配A和/或B的字母，则设X是A和B的最小超序列。

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

接受A和B的最小超序列的 DFA 最多可以使用|A|*|B|状态，每个状态对应于两个字符串中的一对兼容位置。 查看 https://en.wikipedia.org/wiki/Deterministic_finite_automaton 和 https://en.wikipedia.org/wiki/Powerset_construction

如果存在 A和B的超序列不是 F 的超序列，则有一条通过此 DFA 的路径不是F的超序列。

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

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

IFF任何接受州的最低成本都低于|F|，则存在A和B的超序列，它不是F的超序列。

整个操作的复杂度为O(|A|*|B|(

实现此目的的最简单方法是使用|A|+1x |B|+1矩阵作为 DFA -- 就像您用于 LCS 计算的矩阵一样。 矩阵中的每个单元格都是一个状态。 当发现细胞时，用它们的最低成本填充它们。

Answer 2

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

这个想法是遍历 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";