题解 | #最长公共子串#

'''
解题思路：
动态规划算法，
dp[i][j]定义为：str1在索引i处，str2在索引j处，存在公共子串的最大长度（即至少存在str1[i]==str2[j]）
               需要记录所有的ij处存在公共子串的最大长度，及对应的i或j（子串终点）               
1、当i==0 | j==0：
   (a)当str1[i] == str2[j]，dp[i][j] = 1
2、其它情况：
   (b)当str1[i] == str2[j]，dp[i][j] = dp[i-1][j-1] + 1
#=============================================================================================
'''
#
# 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
        r = len(str1)
        c = len(str2)
        dp = [[0]*c for _ in range(r)]
        maxlen = 0
        endstr1 = 0
        for i in range(r):
            for j in range(c):
                if (i==0 or j==0):
                    if str1[i]==str2[j]:                    
                        dp[i][j] = 1
                else:
                    if str1[i]==str2[j]:  
                        dp[i][j] = dp[i-1][j-1]+1

                if dp[i][j]>maxlen:
                    maxlen = dp[i][j]
                    endstr1 = i

        #for i in dp:
        #    print(i)

        if maxlen>0:
            return str1[endstr1-maxlen+1:endstr1+1]

str1 = '1AB2345CD'
str2 = '12345EF'
s = Solution()
print(s.LCS(str1,str2))