python求两个字符串的最长公共子串(动态规划法)(如abccade和dgcadde最长公共子串为cad)

#求两个字符串的最长公共子串(动态规划法)
def getMaxSub(str1,str2):n1=len(str1)n2=len(str2)s=[] #公共子串maxs=0 #最长公共子串的长度maxI=0 #记录最长公共子串最后一个字符的位置list1=list(str1)list2=list(str2)M=[([None]*(n1+1)) for i in range(n2+1)] #(n1+1)*(n2+1)维空矩阵，记录公共子串for i in range(n1+1):M[i][0]=0for j in range(n2):M[0][j]=0 for i in range(n1): #将公共字串的长度信息填写到二维数组中for j in range(n2):if list1[i]==list2[j]:M[i+1][j+1]=M[i][j]+1if M[i+1][j+1]>maxs:maxs=M[i+1][j+1]maxI=i+1else:M[i+1][j+1]=0                for i in range(maxI-maxs,maxI):s.append(list1[i])result=''.join(s)print(result)
if __name__ == '__main__':str1='abccade'str2='dgcadde'getMaxSub(str1,str2) #结果为cad