python - 最长公共(public)子串矩阵

Question

我是 python 的新手，正在努力创建一个表示最长公共(public)子字符串的矩阵。我正在寻找这样的结果: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]

但是我的结果是一个显示不正确值的矩阵。当我手动计算矩阵时，正确的输出如下所示:Correct output .我觉得我的逻辑是有道理的，我做错了什么？

谢谢大家

Answer 1

首先，为了清楚起见，longest common subsequence问题与longest common substring不一样问题。您要解决的是后者；最好不要混淆两者。

其次，你的else分支未在适当的 if 下对齐状况。每当字符串匹配 X[i] == Y[j] ，如果索引 i 或 j 为 0，我们将矩阵元素设置为 1，因为 i-1 或 j-1 在 0 处给出 -1(不幸的是，这也是 Python 中最后一项的索引)这不是我们想要的，否则我们增加更高的索引 i, j > 1。

第三，你的循环应该从 0 而不是 1 开始，因为我们从字符串中索引为 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, <b>1</b>, 0, 0, 0, 2, 0, 0]
[0, 0, 0, <b>2</b>, 0, 0, 0, 0, 0]
[0, 0, 0, 0, <b>3</b>, 1, 0, 0, 1]
[0, 0, 0, 0, 1, <b>4</b>, 0, 0, 1]
[1, 1, 0, 0, 0, 0, 0, 1, 0]