def LCS(self , str1 , str2 ):
#动态规划
m,n=len(str1),len(str2)
maxLen,endIndex=0,0
dp=[[0 for t in range(n)] for x in range(m)]
for i in range(m):
for j in range(n):
if str1[i]==str2[j]:
if i==0 or j==0:dp[i][j]=1
else:dp[i][j]=dp[i-1][j-1]+1
if dp[i][j]>maxLen:
endIndex=i
maxLen=dp[i][j]
else:dp[i][j]=0
return str1[endIndex-maxLen+1:endIndex+1]