写在前面
首先解释一下二者的区别，最长公共子序列(LCS)允许两个公共的子序列在原有的两个字符串中不连续，即ABCFD与EACFB，二者的最长公共子序列为ACF；而最长公共子串，要求连续，其最长公共子串为CF。
1. 最长公共子序列
描述：给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。
题目链接：https://www.lintcode.com/problem/longest-common-subsequence/description
最长公共子序列的定义：：
最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。
https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
样例 1:
输入: "ABCD" and "EDCA"
输出: 1
解释:
LCS 是 'A' 或 'D' 或 'C'
样例 2:
输入: "ABCD" and "EACB"
输出: 2
解释:
LCS 是 "AC"
思路：
这种双序列动态规划的题目，一般是考虑如下几种情况：
- 最后一步和子问题：
- 字符串A和字符串B的最后一个元素不相同，那其公共子序列需要用A[:n - 1] 和B或者**A和B[m - 1]去找。
- 字符串A和字符串B的最后一个元素 相同，那其公共子序列需要用A[:n - 1] 和[m - 1]去找。
-
转移方程：
使用一个二维矩阵去记录两个字符串的子序列之间最大公共子序列长度。
image - 初始条件及边界条件：
当序列为空是，与其他子序列的公共子序列长度为空。因此，需要再加一维，记录空序列的长度(即，长度为0)。 - 计算顺序
从上到下，从左到右。
image.png
代码实现：
class Solution:
"""
@param A: A string
@param B: A string
@return: The length of longest common subsequence of A and B
"""
def longestCommonSubsequence(self, A, B):
# write your code here
if A == '' or B == '':
return 0
n = len(A)
m = len(B)
dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
for i in range(1, n+1):
for j in range(1, m+1):
if A[i - 1] == B[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
1.1 进阶
还原最长公共子序列，也就是把公共子序列打印出来。
这里需要再追加一个辅助数组flags数组，这个数组的维度和刚才的dp数组相同。这个数组主要是用来记录dp数组的每一步都执行了什么操作。用3来表示A[i - 1] == B[j - 1]，用1来表示dp[i][j] = dp[i - 1][j]，用2来表示dp[i][j] = dp[i][j - 1]。我们从最后一个元素开始还原，就是需要找到标记为3的坐标位置，然后根据A或者B还原出公共子序列。
具体代码如下：
class Solution:
"""
@param A: A string
@param B: A string
@return: The length of longest common subsequence of A and B
"""
def longestCommonSubsequence(self, A, B):
# write your code here
if A == '' or B == '':
return 0
n = len(A)
m = len(B)
dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
flags = [[0 for j in range(m + 1)] for i in range(n + 1)] # 辅助标记数组
for i in range(1, n + 1):
for j in range(1, m + 1):
if A[i - 1] == B[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
flags[i - 1][j - 1] = 3
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
if dp[i - 1][j] == dp[i][j]:
flags[i - 1][j] = 1
else:
flags[i][j - 1] = 2
s = ['' for i in range(dp[n][m])]
p = dp[n][m] - 1
row = n
col = m
while row > 0 and col > 0:
if flags[row][col] == 1:
row -= 1
elif flags[row][col] == 2:
col -= 1
else:
s[p] = A[row - 1]
p -= 1
row -= 1
col -= 1
return s
if __name__ == '__main__':
s = Solution()
A = 'abcd'
B = 'wwawwbwwdwwwcwwd'
print(s.longestCommonSubsequence(A,B))
2. 最长公共子串
题目链接：https://www.lintcode.com/problem/longest-common-substring/description
题目描述：给出两个字符串，找到最长公共子串，并返回其长度。
样例 1:
输入: "ABCD" and "CBCE"
输出: 2
解释:
最长公共子串是 "BC"
样例 2:
输入: "ABCD" and "EACB"
输出: 1
解释:
最长公共子串是 'A' 或 'C' 或 'B'
- 给出一个时间复杂度为O(n^2)的解法,这种方法效率太低。
class Solution:
"""
@param A: A string
@param B: A string
@return: the length of the longest common substring.
"""
def longestCommonSubstring(self, A, B):
# write your code here
if A == '' or B == '':
return 0
max_len = 0
for i in range(len(A)):
for j in range(i, len(A)):
s = A[i:j+1]
if s in B:
max_len = max(max_len, len(s))
return max_len
- 下面给出优化：
和最长公共子序列的做法基本一致，只是有了连续的要求，因此，状态转移方程需要改一下：
image.png
而且返回的也是最后一个结果了，需要一个max_length变量来记录最大长度。
class Solution:
"""
@param A: A string
@param B: A string
@return: the length of the longest common substring.
"""
def longestCommonSubstring(self, A, B):
# write your code here
if A == '' or B == '':
return 0
n = len(A)
m = len(B)
dp = [[0 for j in range(m + 1)] for i in range(n + 1)]
max_length = 0
for i in range(1, n+1):
for j in range(1, m+1):
if A[i - 1] == B[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = 0
max_length = max(max_length, dp[i][j])
return max_length
