最长公共子串矩阵

Question

最长公共子串矩阵

3

我很新手，不太懂Python，在创建一个表达最长公共子串的矩阵方面遇到了一些困难。我希望得到像这样的结果：LCS matrix

这是目前为止我的代码：

def compute_lcs(X, Y):
    m = len(X)
    n = len(Y)
# An (m) times (n) matrix
    matrix = [[0] * (n) for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            if X[i] == Y[j]: 
                if i == 0 or j == 0:
                    matrix[i][j] = 1
            else:
                matrix[i][j] = matrix[i-1][j-1]+1
        else:
            matrix[i][j] = 0
    return matrix

b = compute_lcs('AACTGGCAG','TACGCTGGA')
for y in b:
    print (y)

Current Output:
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 1, 0]
[0, 1, 0, 2, 0, 2, 2, 2, 0]
[0, 1, 2, 1, 3, 0, 3, 3, 0]
[0, 1, 2, 0, 2, 4, 0, 0, 0]
[0, 1, 2, 0, 1, 3, 0, 0, 0]
[0, 1, 0, 3, 0, 2, 4, 1, 0]
[0, 0, 2, 1, 4, 1, 3, 5, 0]
[0, 1, 1, 0, 2, 5, 0, 0, 0]

Expected Output:
[0, 0, 0, 1, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 2, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 1, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 2, 0, 0]
[0, 0, 0, 2, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 3, 1, 0, 0, 0]
[0, 0, 0, 0, 1, 4, 0, 0, 1]
[1, 1, 0, 0, 0, 0, 0, 1, 0]

然而我的结果是一个矩阵，显示的值是错误的。当我手动计算矩阵时，正确的输出应该是这样的：正确的输出。我感觉我的逻辑是有道理的，那么哪里出了问题呢？

谢谢大家。

- Chris Lin

1

你能否把输出作为问题的一部分而不是图片呈现出来吗？这样更容易比较和查看哪些地方出了问题。 - Karl

已修复。感谢您的反馈。 - Chris Lin

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Moses Koledoye · Accepted Answer

首先，为了澄清事情，最长公共子序列问题与最长公共字串问题不同。你要解决的是后者；最好不要混淆这两个问题。

其次，你的else分支没有对应的if条件对齐。每当字符串匹配X[i] == Y[j]，如果索引i或j为0，则将矩阵元素设置为1，因为在索引i-1或j-1处为0时会给出-1（不幸的是，这也是Python中的最后一个项目索引），这不是我们想要的，否则我们会增加更高的索引i、j > 1。

第三，循环应该从0开始，因为我们从索引0开始处理字符串的第一个字符：

def compute_lcs(X, Y):
   m = len(X)
   n = len(Y)
   # An (m) times (n) matrix
   matrix = [[0] * n for _ in range(m)]
   for i in range(0, m):
      for j in range(0, n):
          if X[i] == Y[j]: 
              if i == 0 or j == 0:
                  matrix[i][j] = 1
              else:
                  matrix[i][j] = matrix[i-1][j-1]+1
          else:
              matrix[i][j] = 0
  return matrix

要获得与期望输出相同的矩阵，您应该在打印之前交换参数的顺序或转置矩阵。但请注意，这些操作并非必需（交换或转置），仅用于格式化目的。

b = compute_lcs('TACGCTGGA', 'AACTGGCAG')
for y in b:
    print (y)

[0, 0, 0, 1, 0, 0, 0, 0, 0] [1, 1, 0, 0, 0, 0, 0, 1, 0] [0, 0, 2, 0, 0, 0, 1, 0, 0] [0, 0, 0, 0, 1, 1, 0, 0, 1] [0, 0, 1, 0, 0, 0, 2, 0, 0] [0, 0, 0, 2, 0, 0, 0, 0, 0] [0, 0, 0, 0, 3, 1, 0, 0, 1] [0, 0, 0, 0, 1, 4, 0, 0, 1] [1, 1, 0, 0, 0, 0, 0, 1, 0]