3

我知道 LCS 问题需要时间 ~ O(m n) 其中 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 个元素而没有找到共同元素时，结果都会返回 False。有人说应该有一个和 O(Q*n) 一样好的算法，但我想不通。

更新：已经找到答案了！

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

4

2 回答 2

0

您也可以说使字符串相等的过程成本不得大于 Q。如果大于 Q，则答案必须为假。（编辑距离问题）

假设字符串 x 的大小为 m，字符串 y 的大小为 n，那么我们创建一个二维数组 d[0..m][0..n]，其中 d[i][j] 表示编辑x 的 i 长度前缀和 y 的 j 长度前缀之间的距离。

数组 d 的计算是使用动态规划完成的，它使用以下递归：

d[i][0] = i , for i <= m
d[0][j] = j , for j <= n

d[i][j] = d[i - 1][j - 1], if s[i] == w[j],
d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + 1), otherwise.

LCS的答案 if m>n, m-dp[m][m-n]

于 2014-10-15T09:56:30.717 回答
0

这是一种可能的方法：
1. 假设它f(prefix_len, deleted_cnt)是最左边的位置，Y其中prefix_len的元素X已经被处理并且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)（假设它具有 index pos）f(i + 1, j) = min(f(i + 1, j), pos)：。
4. 所以剩下的唯一问题是如何从给定位置获取位于右侧的最左侧匹配元素。让我们预先计算以下对： (position in Y, element of X) -> 元素 of 的最左边出现Y等于该元素X从该位置 in 到右侧的该元素，Y并将它们放入哈希表中。它看起来像O(n^2)。但不是。对于 中的固定位置Y，我们永远不需要比Q + 1位置更靠右。为什么？如果我们走得更远，我们跳过的不仅仅是Q元素！所以我们可以使用这个事实来只检查O(N * Q)对并获得所需的时间复杂度。当我们有这个哈希表时，发现pos在第 3 步中只是一个哈希表查找。这是此步骤的伪代码：

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)平均具有时间复杂度，不是在最坏的情况下，但它应该是可行的。

于 2014-10-14T18:41:55.323 回答