我知道一般的 LCS 问题和算法。
是这样的:
LCS(Xi, Yj) = [0 (i = 0 or j = 0)
or LCS(Xi-1, Yj-1) + 1 (xi = yj)
or max(LCS(Xi, Yj-1), LCS(Xi-1, Yj)) (xi != yj)]
但是如果我们添加一个间隙条件呢?
例如:
String A is cttauaucagu
String B is cautauatcgu
if no gap condition
lcs = cauauagu
if gap = 1 (lcs gap is under 1)
lcs = auaua
if gap = 0 (lcs gap is under 0)
lcs = taua
视觉呈现:
我该如何解决?
如何制作 DP 表?
最佳答案
这种情况下的解决方案没有太大区别。您必须向 dp 添加另外 2 个参数 - 两个字符串的公共(public)子序列中包含的最后一个元素的索引。然后在 dp 的每一步只搜索给定字符串中的 the_last_included_element 和 the_last_included_elemement + gap + 1 之间的相等元素。
关于algorithm - 如何解决带间隙条件的LCS(最长公共(public)子序列),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19247314/