基本概念
首先，需要搞清楚这是两个不一样的问题，序列要求可以不是连续的，而子串要求必须是连续的。
下面我们将来介绍两个问题的解法，我们采用的方法是以空间换时间的动态规划的问题，对于动态规划，如何写出状态转移方程是问题求解的关键，还需要我们找出问题的起始解是什么。对于一些比较难得问题，我们无法直接应用动态规划，需要做一些变换（其中大部分是数学的思想）
最长公共子串
X=<x1,x2,x3......xn> ,Y=<y1,y2,y3......yn>
首先，我们先写出一个最简单的方法，状态转移方程为：
record[i][j] = record[i-1][j-1]+1
i,j表示以xi和yj结尾的最长公共子串，具体代码如下：
class Solution:
def LongestCommonSubstring(self,text,query):
record = [[0 for i in range(len(query)+1)] for j in range(len(text)+1)]
record[0][0]=0
res,index = 0,0
for i in range(0,len(text)):
for j in range(0,len(query)):
if text[i]==query[j]:
record[i][j] = record[i-1][j-1]+1
else:
record[i][j] = 0
if res<record[i][j]:
res=record[i][j]
index=i
return res,text[index-res+1:index+1]
if __name__ =="__main__":
s = Solution()
text,query = "acaccbabb","acbac"
print s.LongestCommonSubstring(text,query)
上述揭发时间复杂度和空间复杂度均为为O(len(text)*len(query))，按常理，动态规划的空间复杂度是可以优化到1维数组的，需要逆序便利，为什么逆序，
具体如下：
class Solution:
def LongestCommonSubstring(self,text,query):
record = [0 for i in range(len(text)+1)]
res,index = 0,0
for i in range(len(query)):
for j in range(len(text)-1,0,-1):
if query[i]==text[j]:
record[j] = record[j-1]+1
else:
record[j] = 0
if res<record[j]:
res=record[j]
index=j
return res,text[index-res+1:index+1]
if __name__ =="__main__":
s = Solution()
text,query = "acaccbabb","acbac"
print s.LongestCommonSubstring(text,query)
最长公共子序列
相对于上一个问题，这个问题更难一点，首先还是要写出状态转移方程：
if text[i-1]==query[j-1]: record[i][j]=record[i-1][j-1]+1 else: record[i][j] = max(record[i-1][j],record[i][j-1])
代码如下：
class Solution:
def LongestCommonSubSequeence(self,text,query):
record = [[0 for j in range(len(query)+1)] for i in range(len(text)+1)]
for i in range(len(text)+1):
record[i][0] = 0
for j in range(len(query)+1):
record[0][j] = 0
for i in range(1,len(text)+1):
for j in range(1,len(query)+1):
if text[i-1]==query[j-1]:
record[i][j]=record[i-1][j-1]+1
else:
record[i][j] = max(record[i-1][j],record[i][j-1])
return record[len(text)][len(query)]
if __name__ =="__main__":
s = Solution()
text,query = "acaccbabb","acbac"
print s.LongestCommonSubSequeence(text,query)
以上就是最长公共子串与最长公共子序列的解法
