1. 什么是最长公共子序列？什么是最长公共子串？

1.1. 最长公共子序列（Longest-Common-Subsequences，LCS）

最长公共子序列（Longest-Common-Subsequences，LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的问题。这与查找最长公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。

最长公共子序列问题是一个经典的计算机科学问题，也是数据比较程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。

1.2 最长公共子串（Longest-Common-Substring，LCS）

最长公共子串（Longest-Common-Substring，LCS）问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的，而子串却必须是连续的。

2. 如何求解最长公共子序列?

例如序列str_a=world，str_b=wordl。序列wo是str_a和str_b的一个公共子序列，但是不是str_a和str_b的最长公共子序列，子序列word是str_a和str_b的一个LCS，序列worl也是。

暴力查找？

寻找LCS的一种方法是枚举X所有的子序列，然后注意检查是否是Y的子序列，并随时记录发现的最长子序列。假设X有m个元素，则X有2^m个子序列，指数级的时间，对长序列不实际。

分析问题，设str_a=<x1,x2,…,xm>和str_b=<y1,y2,…,yn>为两个序列，LCS(str_a,str_b)表示str_a和str_b的一个最长公共子序列，可以看出

如果str_a[m] == str_b[n]，则LCS (str_a, str_b) = str_a[m] + LCS(str_a[1:m-1],str_b[1:n-1])

如果str_a[m] != str_b[n]，则LCS(str_a,str_b)= max{LCS(str_a[1:m-1], str_b), LCS (str_a, str_b[n-1])}

LCS问题也具有重叠子问题性质：为找出LCS(str_a,str_b)，可能需要找LCS(str_a[1:m-1], str_b)以及LCS (str_a, str_b[n-1])。但这两个子问题都包含着LCS(str_a[1:m-1],str_b[1:n-1]).

2.1 基于递归的方法

根据上边分析结果，可以写出简洁易懂的递归方法。

def recursive_lcs(str_a, str_b):

  if len(str_a) == 0 or len(str_b) == 0:

    return 0

  if str_a[0] == str_b[0]:

    return recursive_lcs(str_a[1:], str_b[1:]) + 1

  else:

    return max([recursive_lcs(str_a[1:], str_b), recursive_lcs(str_a, str_b[1:])])

print recursive_lcs(str_a, str_b)

2.2 基于自底向上动态规划的方法

根据上述分析问题，动态规划递推公式也非常明显，可以写出动态规划代码：

def bottom_up_dp_lcs(str_a, str_b):

  """

  longest common subsequence of str_a and str_b

  """

  if len(str_a) == 0 or len(str_b) == 0:

    return 0

  dp = [[0 for _ in range(len(str_b) + 1)] for _ in range(len(str_a) + 1)]

  for i in range(1, len(str_a) + 1):

    for j in range(1, len(str_b) + 1):

      if str_a[i-1] == str_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]])

  print "length of LCS is :",dp[len(str_a)][len(str_b)]

  # 输出最长公共子序列

  i, j = len(str_a), len(str_b)

  LCS = ""

  while i > 0 and j > 0:

    if str_a[i-1] == str_b[j-1] \   # 这里一定要比较a[i-1]和b[j-1]是否相等

        and dp[i][j] == dp[i-1][j-1] + 1:

      LCS = str_a[i - 1] + LCS

      i, j = i-1, j-1

      continue

    if dp[i][j] == dp[i-1][j]:

      i, j = i-1, j

      continue

    if dp[i][j] == dp[i][j-1]:

      i, j = i, j-1

      continue

  print "LCS is :", LCS

bottom_up_dp_lcs(str_a, str_b)

2.3 降低空间复杂度的动态规划算法

根据上述问题分析以及2.2中的dp矩阵可以看出，其实每一步的求解，只和三个元素有关：左边的元素，上边的元素，左上角的元素。因此我们可以进行空间优化，用一维数组代替二维矩阵。

def space_efficient_lcs(str_a, str_b):

  """

  longest common subsequence of str_a and str_b, with O(n) space complexity

  """

  if len(str_a) == 0 or len(str_b) == 0:

    return 0

  dp = [0 for _ in range(len(str_b) + 1)]

  for i in range(1, len(str_a) + 1):

    left_up = 0

    dp[0] = 0

    for j in range(1, len(str_b) + 1):

      left = dp[j-1]

      up = dp[j]

      if str_a[i-1] == str_b[j-1]:

        dp[j] = left_up + 1

      else:

        dp[j] = max([left, up])

      left_up = up

  print dp[len(str_b)]

space_efficient_lcs(str_a, str_b)

3. 如何求解最长公共子串？

最长公共子串比最长公共子序列的递推公式要简单一些。

dp[i][j]的含义也发生了变化：

• 在最长公共子序列中，dp[i][j]表示str_a[1:i]和str_b[1:j]的最长公共子序列，是从str_a的1和str_b的1开始计算的，即整个字符串的起始位置。
• 在最长公共子串中，dp[i][j]表示str_a[i':i]和str_b[j':j]的最长公共子串，因为str_a和str_b可能存在多个公共子串，所以i'和j'分别表示当前公共子串的起始位置。

也就是说：

• 当str_a[i] == str_b[j]时，dp[i][j] = dp[i-1][j-1]+ 1；
• 当str_a[i] != str_b[j]时，dp[i][j] = 0，即开始计算新的公共子串。

和最长公共子序列不同的是，在最长公共子串问题中，dp[m][n]不一定是最终结果，比如“abcdxy”和“abcfxy”，dp[m][n]存储的是公共子串“xy”的长度，而不是公共子串“abc”的长度，所以需要一个变量单独记录最长子串的长度。

3.1 动态规划算法

def bottom_up_dp_lcs(str_a, str_b):

  """

  longest common substring of str_a and str_b

  """

  if len(str_a) == 0 or len(str_b) == 0:

    return 0

  dp = [[0 for _ in range(len(str_b) + 1)] for _ in range(len(str_a) + 1)]

  max_len = 0

  lcs_str = ""

  for i in range(1, len(str_a) + 1):

    for j in range(1, len(str_b) + 1):

      if str_a[i-1] == str_b[j-1]:

        dp[i][j] = dp[i-1][j-1] + 1

        max_len = max([max_len, dp[i][j]])

        if max_len == dp[i][j]:

          lcs_str = str_a[i-max_len:i]

      else:

        dp[i][j] = 0

  print "length of LCS is :",max_len

  print "LCS :",lcs_str

bottom_up_dp_lcs(str_a, str_b)

3.2 优化空间复杂度的动态规划算法

def space_efficient_lcs(str_a, str_b):

  """

  longest common substring of str_a and str_b, with O(n) space complexity

  """

  if len(str_a) == 0 or len(str_b) == 0:

    return 0

  max_len = 0

  dp = [0 for _ in range(len(str_b) + 1)]

  for i in range(1, len(str_a) + 1):

    left_up = 0

    for j in range(1, len(str_b) + 1):

      up = dp[j]

      if str_a[i-1] == str_b[j-1]:

        dp[j] = left_up + 1

        max_len = max([max_len, dp[j]])

      else:

        dp[j] = 0

      left_up = up

  print max_len

space_efficient_lcs(str_a, str_b)