最长公共子串与最长公共子序列
子串（Substring）是串的一个连续的部分，子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串acdfg同akdfc的最长公共子串为df，而他们的最长公共子序列是adf。
最长公共子串
假设已知s1[0:i－1],s2[0:j－1]从右往左数的最长公共子串长度，那么两字符串同时右移一位，如果s1[i]==s2[j],则s1[0:i],s2[0:j]在i，j位置的最长公共子串长度是s1[0:i－1],s2[0:j－1]从右往左数的最长公共子串长度＋1，否则是0，用a[i][j]记录此长度，状态转移方程如下：
if s1[i]==s2[j]{
a[i][j]=a[i-1][j-1]+1
}else{
a[i][j]=0
}
用到了i-1,j-1,所以两个都递增，初始化都为0，如果两个首字母相同a[0][0:j]=1,a[0:i][0]=1
最长公共子序列
假设已知s1[0:i-1],s2[0:j-1]的最长公共子序列，如果s1[i]==s2[j],则，s1[0:i],s2[0:j]的长度为s1[0:i-1],s2[0:j-1]的最长公共子序列＋1，否则取s1[0:i],s2[0:j-1] 与s1[0:i-1],s2[0:j]中的大者，同a[i][j]记录最长公共子序列的长度，状态转移方程为：
if s1[i]==s2[j]{
a[i][j]=a[i-1][j-1]+1
}else{
a[i][j]=max(a[]i)[j-1],a[i-1][j])
}
用到了i-1,j-1,所以两个都递增，初始化都为0，如果两个首字母相同a[0][0:j]=1,a[0:i][0]=1