思路：动态规划。
dp[i][j]标识str1[i]和str[j]结尾的最长公共子串，递推关系如下：
- 若
str1[i] == str2[j]，则dp[i][j] = dp[i-1][j-1] + 1 - 否则，
dp[i][j] = 0
class Solution:
def LCS(self,str1 , str2 ):
# write code here
len1, len2= len(str1), len(str2)
dp = [[0 for j in range(len2)] for i in range(len1)]
for i in range(len1):
dp[i][0] = 1 if str1[i] == str2[0] else 0
for j in range(len2):
dp[0][j] = 1 if str1[0] == str2[j] else 0
maxlen = 0
pos = 0
for i in range(1,len1):
for j in range(1, len2):
if str1[i] == str2[j]:
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > maxlen:
maxlen = dp[i][j]
pos = i
else:
dp[i][j] = 0
return str1[pos-maxlen+1:pos+1]
