打印最长的常见序列

Question

我试图实现经典问题的解决方案，但我很困惑，因为我在某些情况下找不到好的结果。

输出： “最长的共同序列”， “长度”

def longestCommonSeq(x,y): 
    LCS = [[0 for z in range(len(y)+1)] for z in range(len(x)+1)] 
    for i in range(len(x)): 
     LCS[i][0]=0 

    for j in range(len(y)): 
     LCS[0][j]=0 

    for i in range(len(x)): 
     for j in range(len(y)): 
      if x[i]== y[j]: 
       LCS[i][j]= 1+LCS[i-1][j-1] 
      else: 
       LCS[i][j]= max(LCS[i-1][j],LCS[i][j-1]) 


    i, j= len(x),len(y) 
    print LCS 

    res = "" 
    while i>0 and j>0: 

     if x[i-1]== y[j-1]: 
      res= x[i-1] + res 
      i-=1 
      j-=1 
     else: 
      if LCS[i-1][j]>LCS[i][j-1]: 
       i-=1 
      else: 
       j-=1 

    return res, LCS[len(x)-1][len(y)-1] 

对于第一种情况：

x= "AGGTAB" 
y= "GXTXAYB" 
print longestCommonSeq(x,y) 

结果：('GTAB', 4) 这是正确的！

但对于像案例：

a= "APBCADCQER" 
b= "RASBTAUCVE" 
print longestCommonSeq(a,b) 

('', 5) 

我错过了什么，谁能给一个提示？

Answer 1

你正在建造错误的表;您应该将行保留在i = 0并将j = 0的列全部保留为0，并将匹配置于较高的行中。这意味着您需要在第一个循环中的i和j坐标中加1，因为Python的索引开始为0.

因此，最后会出现一个表，其结尾为0;使用类似于explanation on Wikipedia你基本上是建立这个符号：

┌─┬─────┬─────────┬─────────┬─────┬──────┬───────┬─┐ 
│ │A │G  │G  │T │A  │B  │ │ 
├─┼─────┼─────────┼─────────┼─────┼──────┼───────┼─┤ 
│G│<^0│\ G  │\ G  │< G │< G │< G │0│ 
├─┼─────┼─────────┼─────────┼─────┼──────┼───────┼─┤ 
│X│<^0│^ G  │<^G │<^G│<^G │<^G │0│ 
├─┼─────┼─────────┼─────────┼─────┼──────┼───────┼─┤ 
│T│<^0│^ G  │<^G │\ GT │< GT │< GT │0│ 
├─┼─────┼─────────┼─────────┼─────┼──────┼───────┼─┤ 
│X│<^0│^ G  │<^G │^ GT │<^GT│<^GT │0│ 
├─┼─────┼─────────┼─────────┼─────┼──────┼───────┼─┤ 
│A│\ A │<^A | G│<^A | G│^ GT │\ GTA │< GTA │0│ 
├─┼─────┼─────────┼─────────┼─────┼──────┼───────┼─┤ 
│I│^ A │<^A | G│<^A | G│^ GT │^ GTA │<^GTA│0│ 
├─┼─────┼─────────┼─────────┼─────┼──────┼───────┼─┤ 
│B│^ A │<^A | G│<^A | G│^ GT │^ GTA │\ GTAB │0│ 
├─┼─────┼─────────┼─────────┼─────┼──────┼───────┼─┤ 
│ │0 │0  │0  │0 │0  │0  │0│ 
└─┴─────┴─────────┴─────────┴─────┴──────┴───────┴─┘ 

< and ^: maximum picked 
\: add matching character to cell to the top left. 

这是离开你的最后一列和行设置为0，而不是第一个。 Python将-1解释为最后一个元素是你的运气，因为在i = 0或j = 0这正是你最终做的。你想代替的是：

┌─┬─┬─────┬─────────┬─────────┬─────┬──────┬───────┐ 
│ │ │A │G  │G  │T │A  │B  │ 
├─┼─┼─────┼─────────┼─────────┼─────┼──────┼───────┤ 
│ │0│0 │0  │0  │0 │0  │0  │ 
├─┼─┼─────┼─────────┼─────────┼─────┼──────┼───────┤ 
│G│0│<^0│\ G  │\ G  │< G │< G │< G │ 
├─┼─┼─────┼─────────┼─────────┼─────┼──────┼───────┤ 
│X│0│<^0│^ G  │<^G │<^G│<^G │<^G │ 
├─┼─┼─────┼─────────┼─────────┼─────┼──────┼───────┤ 
│T│0│<^0│^ G  │<^G │\ GT │< GT │< GT │ 
├─┼─┼─────┼─────────┼─────────┼─────┼──────┼───────┤ 
│X│0│<^0│^ G  │<^G │^ GT │<^GT│<^GT │ 
├─┼─┼─────┼─────────┼─────────┼─────┼──────┼───────┤ 
│A│0│\ A │<^A | G│<^A | G│^ GT │\ GTA │< GTA │ 
├─┼─┼─────┼─────────┼─────────┼─────┼──────┼───────┤ 
│I│0│^ A │<^A | G│<^A | G│^ GT │^ GTA │<^GTA│ 
├─┼─┼─────┼─────────┼─────────┼─────┼──────┼───────┤ 
│B│0│^ A │<^A | G│<^A | G│^ GT │^ GTA │\ GTAB │ 
└─┴─┴─────┴─────────┴─────────┴─────┴──────┴───────┘ 

接下来，你不需要在第二循环中进行协商x和y，你咨询只是你LCS表。因为最后是0，总是在最后一行和最后一列中，当x和y的最后一个字符不匹配时，算法的版本将保持不变，并且当您未能击中时，您最终会几乎随机地减少i和j表中列出的LCS路径。

请注意，您的前两个for循环是完全多余的，可以删除;您的整个LCS表只包含0值，为什么将它们设置为0一些？ Wikipedia中的伪代码使用从1到长度（包含）的循环，但是由于Python从0开始，并且将长度加1以保持包含长度，所以不需要在此处执行此操作。然后

你纠正功能看起来像：

def longestCommonSeq(x,y): 
    LCS = [[0 for z in range(len(y) + 1)] for z in range(len(x) + 1)] 
    for i in range(len(x)): 
     for j in range(len(y)): 
      if x[i] == y[j]: 
       LCS[i + 1][j + 1] = 1 + LCS[i][j] 
      else: 
       LCS[i + 1][j + 1] = max(LCS[i][j + 1], LCS[i + 1][j]) 

    res = '' 
    i, j = len(x), len(y) 

    while i and j: 
     if LCS[i][j] == LCS[i-1][j]: 
      i -= 1 
     elif LCS[i][j] == LCS[i][j-1]: 
      j -= 1 
     else: 
      res = x[i-1] + res 
      i -= 1 
      j -= 1 

    return res, LCS[-1][-1] 

因为LCS表现正确建立，我们可以使用LCS[-1][-1]作为最大长度值太大。

这产生了预期的结果：

>>> x = "AGGTAB" 
>>> y = "GXTXAYB" 
>>> print longestCommonSeq(x, y) 
('GTAB', 4) 
>>> a = "APBCADCQER" 
>>> b = "RASBTAUCVE" 
>>> print longestCommonSeq(a, b) 
('ABACE', 5) 

的替代方案将是固定关断接一个在第二阶段，并期待在实际对应于您的输入字的LCS表格单元;例如从i和j减去1：分别

def longestCommonSeq(x,y): 
    LCS = [[0 for z in range(len(y)+1)] for z in range(len(x)+1)] 

    for i in range(len(x)): 
     for j in range(len(y)): 
      if x[i] == y[j]: 
       LCS[i][j] = 1 + LCS[i - 1][j - 1] 
      else: 
       LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]) 

    i, j = len(x) - 1, len(y) - 1 
    print LCS 

    res = "" 
    while i >= 0 and j >= 0: 
     if x[i] == y[j]: 
      res= x[i] + res 
      i -= 1 
      j -= 1 
     else: 
      if LCS[i - 1][j] > LCS[i][j - 1]: 
       i -= 1 
      else: 
       j -= 1 

    return res, LCS[len(x) - 1][len(y) - 1] 

现在i和j范围len(x) - 1到0和len(y) - 1到0，并且再次引用正确的细胞。