最长公共子序列 (LCS = Longest Common Subsequence) 和最长公共子串 (LCS = Longest Common Substring)

两个序列a,b, L[i][j]为以a[i]和b[j]结尾的最长公共子序列的长度。a长度为m, b长度为n

Longest Common Subsequence (子序列无需连续）

Initial condition:
L[0][j] = (a[0] == b[j]) ? 1 : 0     j = 0...n
L[i][0] = (a[i] == b[0]) ? 1 : 0     i = 0...m
Recurrence relation:
L[i][j] = (a[i] == b[j])  ? L[i-1][j-1] + 1 : max(L[i][j-1], L[i-1][j])    i = 1...m, j = 1...n

最后L[m][n]即为结果

 Longest Common Substring（子串需要连续）

Initial condition:
a[0][j] = (a[0] == b[j]) ? 1 : 0     j = 0...n
a[i][0] = (a[i] == b[0]) ? 1 : 0     i = 0...m
Recurrence relation:
L[i][j] = (a[i] == b[j])  ? L[i-1][j-1] + 1 : 0   i = 1...m, j = 1...n结果为计算过程中最大的L[i][j] (用一个max变量跟踪）