动态规划：最长公共子序列

Question

我将复习在寻找两个等长字符串的最长公共子序列的上下文中讨论动态规划的笔记。有问题的算法输出长度（不是子串）。

所以我有两个字符串，比如：

S = ABAZDC，T = BACBAD

最长公共子序列是 ABAD（子串不必是相邻的字母）

算法如下，其中LCS[i,j]表示S[1..i]和T[1..j]的最长公共子序列：

if S[i] != T[j] then
    LCS[i, j] = max(LCS[i - 1, j], LCS[i, j - 1])
else
    LCS[i, j] = 1 + LCS[i - 1, j - 1]

我的笔记声称您可以填写一个 table，其中每个字符串都沿着一个轴书写。类似于：

B A C B A D

A 0 1 1 1 1 1

B 1 1 1 2 2 2

一个...

Z

D

C

两个问题：

1) 我们如何真正开始填写这个 table。算法是递归的，但似乎没有提供基本情况（否则我只会调用 LCS[5, 5]）？笔记声称你可以用 i 和 j 做两个简单的循环，并在恒定时间内填写每个点...

2) 我们如何修改算法以使最长公共子序列为相邻字母？我的想法是，一旦我发现 S 中的下一个字母与 T 中的下一个字母不匹配，我就必须将当前子序列的长度重置为 0。但这很棘手，因为我想跟踪最长的到目前为止（我看到的第一个子序列可能是最长的）。所以也许我会有一个额外的参数，longestThusFar，当我们最初调用我们的算法并在后续调用中更改时，它是 0。

有人可以让这更严格一点吗？

谢谢！

Answer 1

首先，该算法是递归的，但实现总是iterative.In换句话说，我们没有显式地从函数本身调用相同的函数（递归）。

我们使用已经填充的 table 个条目来补偿递归。

比如说，你有两个长度为 M.

的字符串

然后table定义了维度(M+1)X(M+1).

for(i = 0 to M)
{
  LCS[0][i]=0;
}
for(i = 1 to M)
{
  LCS[i][0]=0;
}

然后你得到一个 table 赞

    B,A,C,B,A,D
  0,0,0,0,0,0,0
A 0
B 0
A 0
Z 0
D 0
C 0

第 0 列中的每个零 表示如果不考虑字符串 BACBAD 的字符，则 LCS 的长度 = 0.

第第0行中的每个零表示如果不考虑字符串ABAZDC的字符，则LCS的长度= 0。

其余条目使用您提到的规则填写。

for(i = 1 to M)
{
 for(j = 1 to M)
 {
  if S[i-1] != T[j-1] then
    LCS[i, j] = max(LCS[i - 1, j], LCS[i, j - 1])
  else
    LCS[i, j] = 1 + LCS[i - 1, j - 1]
 }
}

注意它是 S[i-1] != T[j-1] 而不是 S[i] != T[j] 因为当你填充 LCS[i,j] 时，你总是在比较 S 的第 i-1 个字符和 T 的第 j-1 个字符。

LCS的长度由LCS[M,M]给出。

理解这一点的最好方法是亲自尝试。

回答你的第二个问题，你不需要对算法做太多修改。

解决方案在于用于检索 LCS 的 table。

为了检索 LCS，我们制作了一个额外的 table T 维度 MXM 的字符。然后我们修改算法如下。

for(i = 1 to M)
{
 for(j = 1 to M)
 {
  if S[i-1] != T[j-1] then
  {
     LCS[i, j] = max(LCS[i - 1, j], LCS[i, j - 1])
     if(LCS[i - 1, j]>=LCS[i, j - 1])          
      T[i-1][j-1]='u'//meaning up
     else T[i-1][j-1]='l'//meaning left
  }
  else
  {
    LCS[i, j] = 1 + LCS[i - 1, j - 1]
    T[i-1][j-1]='d'//meaning diagonally up
  }
 }
}

现在，为了知道两者共有的最长子串（OF ADJACENT LETTERS），对角线遍历 T。

长度 = 在对角线上找到的连续 d 的最大数目。

任意方阵的对角线遍历NXN由.

完成

包含主对角线的下三角

j=N-1
while(j>=0)
{
 i=j;k=0;
 while(i <= N-1)
 {
  entry T[i][k];
  ++i;++k
 }
 --j;
}

上三角

j=1;
while(j<=N-1)
{
 i=j;k=0;
 while(i<=N-1)
 {
  entry T[k][i];
  ++k;++i;
 }
 --j;
}

动态规划：最长公共子序列

Dynamic Programming: Longest Common Subsequence

algorithm

dynamic-programming