python - 找到字符串 X 的最长子序列，它是字符串 Y 的子字符串

Question

我知道如何使用动态规划来解决给定两个字符串找到most 最长公共(public)子序列或最长公共(public)子串的问题。但是，对于查找字符串 X 的最长子序列是字符串 Y 的子字符串 的问题，我很难找到解决方案。

这是我的暴力解决方案:

1. 找出字符串X的所有子序列，并按长度desc排序；
2. 遍历排序后的子序列，如果当前子序列是 Y 的子串，则返回子序列。

它可以工作，但运行时间可能很糟糕。假设 X 中的所有字符都是唯一的，那么有 2^m 个子序列，其中 m 是 X 的长度。我认为检查一个字符串是否是 Y 的子字符串需要 O(n)，其中 n 是 Y 的长度。所以整体运行时间为 O(n*2^m)。

是否有更好的方法，可能是通过 DP？

编辑:

这是我要解决的一个例子:

Y: 'BACDBDCD'
X: 'ABCD'

答案是“ACD”，因为“ACD”是最长的X 的子序列，也是Y 的子串。

Answer 1

这里有两种实现方式(都是多项式时间复杂度)。
1、生成Y的所有子串(有O(m^2)个这样的子串)。对于每个子串，检查它是否是 X 的子序列(可以使用贪心算法在线性时间内完成)。这个算法有O(n * m^2)时间复杂度，已经不错了。
2. 如果不够快，用动态规划可以达到O(n * m)的时间复杂度。让我们定义 f(i, j) = 以 X 中的 i-th 位置和 X 中的 j-th 位置结束的最长答案Y. 转换如下:

f(i + 1, j) = max(f(i + 1, j), f(i, j)) //skip this character in X
if X[i] == Y[j] //add this character to current answer
    f(i + 1, j + 1) = max(f(i + 1, j + 1), f(i, j) + 1)  

对于所有有效的i 和j，f 的初始值为0。 答案是所有有效 j 的 f(n, j) 中的最大值。