题解 | #最长公共子串#

题解:使用python3实现最长公共子串，主要思想是使用动态规划去实现，如果末尾元素相等，则dp[i][j]=dp[i-1][j-1]+1;否则dp[i][j]=0。
重点：dp[i][j]的含义是s[:i]和t[:j]中以s[i-1]和t[j-1]结尾的最长公共子串，因此判断的时候

if s[i-1]==t[j-1]: 
    dp[i][j]=dp[i-1][j-1]+1 
else: 
    dp[i][j]=0

因为题目中强调的是子串，串是连续的，如果将不相等的情况替换成dp[i][j]=max(dp[i-1][j], dp[i][j-1]),这种情况相当于删除后缀，并且是不连续的

# 假设s = "1A2B345CD", t = "2345",最终答案肯定是"345"
# 以dp[5][4]为例，此时s[5]="1A2B3", t[4]="2345",此时的最长公共子串最多是“2”或者“3”；
# 因为s[4]!=t[3]，如果是dp[i][j]=0这种情况，dp[5][4]=0,
# 如果是dp[i][j]=max(dp[i][j-1], dp[i-1][j]),dp[5][4]=max(dp[4][4], dp[5][3]),最终得结果是dp[5][4]=2,此时获得结果是"23"，
# 但这显然不是连续的，因此dp[i][j]的含义只能是s[:i]和t[:j]中以s[i-1]和t[j-1]结尾的最长公共子串，保证后缀是连续的，至于前缀因为dp[i][j]=dp[i-1][j-1]+1的关系，肯定是连续的

由于最终结果是返回字符串，因此要记录最长子串长度和最后的索引位置，这里选择j作为末尾索引，j是作用到str2上的，因此最终return str2[index-max_length:index]

class Solution:
    def LCS(self , str1 , str2 ):
        # write code here
        s = len(str1)
        t = len(str2)
        dp = [[0 for _ in range(t+1)] for _ in range(s+1)]
        max_length = 0
        index = 0
        for i in range(1, s+1):
            for j in range(1, t+1):
                if str1[i-1] == str2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    if max_length < dp[i][j]:
                        max_length = dp[i][j]
                        index = j
                else:
                    dp[i][j] = 0
        print(dp)
        print(max_length)
        print(index)
        return str2[index-max_length:index]