题解 | #最长公共子串#

# -*- coding:utf-8 -*-

class LongestSubstring:
    def findLongest(self, A, n, B, m):
        # write code here
        dp = [ [0 for _ in range(m+1)] for __ in range(n+1) ]
        max_res = 0
        for i in range(1,n+1):
            for j in range(1,m+1):
                # print(i,j,len(A),len(B))
                if A[i-1]==B[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                    max_res = max(max_res,dp[i][j])
        return max_res

和评论区大佬们说的差不多，就是和“最长公共子序列”的题目有点不一样，这个必须得是公共子串，所以在处理A[i]!=B[j]的时候，不管就可以了。dp矩阵的含义就是：当前连续相等的长度。由于这个是从小到大遍历的，所以当A[i]==B[j]的时候会去找dp[i-1][j-1]，如果dp[i-1][j-1]已经大于0（当然等于0也OK），那就说明这之前就已经有连续相等的了，现在再多一个，所以状态转移方程是：dp[i][j]=dp[i-1][j-1]+1，然后如果不等于，那就说明无论去前面找哪个，一旦到了这里都不再是连续的子串了，直接置为0，所以状态转移方程再添加一种情况：dp[i][j] = 0 if A[i]!=B[j]。