0

我对 Python 很陌生，它是我的第一门编程语言，我一直想从事一些手动数据结构操作和玩耍。

我最近一直在学习解决 LCS 问题的基本算法，并且我了解它是如何工作的，除了一行代码，我出于某种奇怪的原因似乎无法说服自己我完全掌握了。

这是我在自己无法完全正确理解之后一直用来学习的代码。

编辑2：无论如何，要使用两个整数列表的输入来完成这项工作？**我发现我正确理解了我的原始问题，但有人知道我如何使用**整数列表来完成这项工作吗？我尝试将 S 和 T 转换为逗号分隔值的字符串，这可以匹配某些字符，但即便如此，它在大多数测试用例中也很少起作用。我不知道为什么它不会，因为它仍然只是比较两个字符串，但是用逗号。

def lcs(S,T):
    m = len(S)
    n = len(T)
    counter = [[0]*(n+1) for x in range(m+1)]
    longest = 0
    lcs_set = set()
    for i in range(m):
        for j in range(n):
            if S[i] == T[j]:
                c = counter[i][j] + 1
                counter[i+1][j+1] = c
                if c > longest:
                    lcs_set = set()
                    longest = c
                    lcs_set.add(S[i-c+1:i+1])
                elif c == longest:
                    lcs_set.add(S[i-c+1:i+1])

    return lcs_set

现在我的问题是理解这一行：lcs_set.add(S[i-c+1:i-1])

我知道当找到匹配项时计数器会增加，以提供最长的子字符串长度。因此，为了简单起见，如果 S = Crow 且 T = Crown，当您到达 w（最后一场比赛）时，计数器将递增到 4，并且 i 在 S 的索引 3 处。

这是否意味着我将其读作：i（S 上的索引 3，W）-c（4），所以 3-4 = -1，所以 3-4+1 = 0（在 C 处）和右侧切片的：i(3) + 1 = 4(N，但显然不包括在内)，这意味着我们以 S[0:4], Crow, to LCS_Set 结尾？

如果是这种情况，我想我很困惑为什么我们将整个子字符串添加到集合中，而不仅仅是最新匹配的字符？

如果我理解正确，它会用当前匹配的子字符串的整个切片更新LCS_set ，所以如果它在第二个匹配项 R 上，计数器将为 2，我为 1，它会说 S[ 1-2+1:i(1)+1]，所以 1-2 = -1, -1 + 1 = 0(C) 直到 i(1)+1 = 2（留下 S[0:2 ] 或 CR)，因此每次都会使用整个子字符串更新集合，而不仅仅是当前索引。

这不是一个真正的问题，我只是想确保我正确理解这一点。

我真的很感激任何输入，或者任何人可能会用我当前的逻辑看到的任何提示！

编辑：

我刚刚意识到我完全忘记了 C 的位置是当前的计数器编号，因此它显然不会用当前的最大匹配数更新 LCS_set，它不能只用当前匹配的字母来更新它，所以它必须获取子字符串的切片才能更新 LCS_Set。提前致谢！

4

0 回答 0