algorithm - 如何解决带间隙条件的LCS(最长公共(public)子序列)

Question

我知道一般的 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 表？

Answer 1

这种情况下的解决方案没有太大区别。您必须向 dp 添加另外 2 个参数 - 两个字符串的公共(public)子序列中包含的最后一个元素的索引。然后在 dp 的每一步只搜索给定字符串中的 the_last_included_element 和 the_last_included_elemement + gap + 1 之间的相等元素。