题解 | #最长公共子串#

#
# longest common substring
# @param str1 string字符串 the string
# @param str2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        m=len(str1)
        n=len(str2)
        dp=[[0 for _ in range(m+1)] for _ in range(n+1)]
        max_temp=-1
        max_dp=0
        for i in range(1,n+1):
            for j in range(1,m+1):
                if str1[j-1]==str2[i-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                    if dp[i][j]>max_dp:
                        max_dp=dp[i][j]
                        max_temp=i-max_dp
                else:
                    dp[i][j]=0
        return str2[max_temp:max_temp+max_dp]