如何计算最长公共子序列的数量

Question

我正在尝试计算两个字符串之间存在的最长可能子序列的数量。

例如字符串 X =“efgefg”；字符串 Y =“efegf”；

输出：最长公共序列的数量为：3（即：efeg、efef、efgf - 这不需要由算法计算，仅在此处显示以进行演示）

我已经根据这里的一般思想使用动态规划在 O(|X|*|Y|) 中成功做到了这一点：最便宜的路径算法。

任何人都可以想出一种方法来以更好的运行时间有效地进行这种计算吗？

——针对杰森的评论进行编辑。

Answer 1

我不知道，但这里有一些大声思考的尝试：

我能够构造的最坏情况具有指数 - 2**(0.5 |X|) - 最长公共子序列的数量：

X = "aAbBcCdD..."
Y = "AaBbCcDd..."

其中最长的公共子序列恰好包含 {A, a} 之一，恰好包含 {B, b} 之一，依此类推...（挑剔：如果你的字母表限制为 256 个字符，这最终会崩溃 - 但是 2** 128已经很大了。）

但是，您不必生成所有子序列来对它们进行计数。如果你有 O(|X| * |Y|)，那么你已经比这更好了！我们从中学到的是，任何比你的算法更好的算法都不能尝试生成实际的子序列。