algorithm - 如何为最长公共(public)子序列 (LCS) 的这种特殊情况找到更快的算法？

Question

我知道 LCS 问题需要时间 ~ O(mn) 其中 m 和 n 分别是两个序列 X 和 Y 的长度。但我的问题有点简单，所以我希望算法比 ~O(mn) 更快。

这是我的问题:

输入:

一个正整数Q，两个序列X=x1,x2,x3.....xn和Y=y1,y2,y3...yn，长度均为n。

输出:

为真，如果X和Y的LCS长度至少为n-Q；

否则为假。

众所周知的算法在这里花费 O(n^2)，但实际上我们可以做得更好。因为每当我们在任一序列中消除尽可能多的 Q 个元素而没有找到公共(public)元素时，结果将返回 False。有人说应该有一个像 O(Q*n) 这样好的算法，但我想不通。

更新: 已经找到答案了!

我被告知我可以只计算表 c[i,j] 的对角线 block ，因为如果 |i-j|>Q，意味着两个序列中已经有超过 Q 个不匹配的元素。所以我们只需要在|i-j|<=Q时计算c[i,j]。

Answer 1

下面是一种可行的方法:
1. 假设 f(prefix_len, deleted_cnt) 是 Y 中最左边的位置，这样 X 的 prefix_len 元素> 已被处理并且恰好 deleted_cnt 被删除。显然，只有O(N * Q)个状态，因为deleted_cnt不能超过Q。
2. 基本情况是 f(0, 0) = 0(未处理任何内容，因此未删除任何内容)。
3. 过渡:
a) 删除当前元素:f(i + 1, j + 1) = min(f(i + 1, j + 1), f(i, j))。
b) 将当前元素与 Y 中与其相等且位于 f(i, j) 之后的最左边可能元素匹配(假设它有索引 pos): f(i + 1, j) = min(f(i + 1, j), pos)。
4. 那么剩下的唯一问题就是如何从给定的位置得到位于右边的最左边的匹配元素。让我们预先计算以下对:(Y 中的位置，X 的元素)-> Y 中元素的最左边出现等于此元素从 Y 中的这个位置向右移动 X 并将它们放入哈希表中。它看起来像 O(n^2)。但不是。对于 Y 中的固定位置，我们永远不需要从它向右移动比 Q + 1 位置更远的位置。为什么？如果我们走得更远，我们将跳过超过 Q 个元素!所以我们可以使用这个事实来仅检查 O(N * Q) 对并获得所需的时间复杂度。当我们有了这个哈希表时，在第 3 步中查找 pos 只是一次哈希表查找。这是此步骤的伪代码:

map = EmptyHashMap()
for i = 0 ... n - 1:
    for j = i + 1 ... min(n - 1, i + q + 1)
        map[(i, Y[j])] = min(map[(i, Y[j])], j)

不幸的是，这个解决方案使用哈希表，所以它的平均时间复杂度为 O(N * Q)，虽然不是最坏的情况，但它应该是可行的。