最长公共子串 / 子序列

本文记录寻找两个字符串最长公共子串和子序列的方法。

名词区别

• 最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence）的区别： 子串要求在原字符串中是连续的，而子序列则只需保持相对顺序，并不要求连续。

最长公共子串

• 是指两个字符串中最长连续相同的子串长度。

  例如：str1=“1AB2345CD”,str2=”12345EF”,则str1，str2的最长公共子串为2345。

动态规划

• 如果 str1 的长度为 $N$，str2 的长度为 $M$，生成大小为 $N*M$ 的 数组 $dp$ , $dp[i][j]$表示 $str1[0…i]$ 与 $str2[0…j]$ 的最长公共子串的长度。

  def find_lcsubstr(s1: str, s2: str): 
      """
      Longest Common Substring
      最长公共子串 (连续串, 非序列)
      O(mn)
  
      Args:
          s1 (str): string 1
          s2 (str): string 2
  
      Returns:
          str: longest_sub_string, max_length
      """
      s1 = str(s1)
      s2 = str(s2)
      # 生成0矩阵，为方便后续计算，比字符串长度多了一列
      m = np.zeros([len(s1) + 1, len(s2) + 1], dtype='uint16')
      mmax = 0   # 最长匹配的长度
      p = 0  # 最长匹配对应在s1中的最后一位
      for i in range(len(s1)):
          for j in range(len(s2)):
              if s1[i] == s2[j]:
                  m[i+1][j+1] = m[i][j] + 1
                  if m[i+1][j+1] > mmax:
                      mmax = m[i+1][j+1]
                      p = i+1
      return s1[p-mmax:p], mmax   # 返回最长子串及其长度

• 该算法:

  • 时间复杂度 $O(MN)$
  • 空间复杂度 $O(MN)$

优化空间复杂度

• 经典动态规划的方法需要大小为$M*N$的$ dp$ 矩阵，但实际上是可以减少至$O(1)$的，因为计算每一个$dp[i][j]$的时候只需要计算$dp[i-1][j-1]$,所以按照斜线方向计算所有的值，只需要一个变量就可以计算。

最长公共子序列

• 子串要求字符必须是连续的，但是子序列就不是这样。

  最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。

• 解法就是用动态回归的思想，一个矩阵记录两个字符串中匹配情况，若是匹配则为左上方的值加1，否则为左方和上方的最大值。一个矩阵记录转移方向，然后根据转移方向，回溯找到最长子序列。

  def find_lcseque(s1: str, s2: str):
      """
      Longest Common Subsequence
      最长公共子序列(不一定连续)
      O(mn)
  
      Args:
          s1 (str): string 1
          s2 (str): string 2
  
      Returns:
          str: Subsequence_str
      """
      #  生成字符串长度加1的0矩阵，m用来保存对应位置匹配的结果
      m = np.zeros([len(s1)+1, len(s2)+1], dtype='uint16')
  
      #  d用来记录转移方向
      d = np.zeros([len(s1)+1, len(s2)+1], dtype='uint8')
  
      for p1 in range(len(s1)): 
          for p2 in range(len(s2)): 
              if s1[p1] == s2[p2]:            # 字符匹配成功，则该位置的值为左上方的值加1
                  m[p1+1][p2+1] = m[p1][p2]+1
                  d[p1+1][p2+1] = 1          
              elif m[p1+1][p2] > m[p1][p2+1]:  # 左值大于上值，则该位置的值为左值，并标记回溯时的方向
                  m[p1+1][p2+1] = m[p1+1][p2] 
                  d[p1+1][p2+1] = 2         
              else:                           # 上值大于左值，则该位置的值为上值，并标记方向up
                  m[p1+1][p2+1] = m[p1][p2+1]   
                  d[p1+1][p2+1] = 3       
  
      (p1, p2) = (len(s1), len(s2)) 
  
      s = [] 
      while m[p1][p2]:    # 不为None时
          c = d[p1][p2]
          if c == 1:   # 匹配成功，插入该字符，并向左上角找下一个
              s.append(s1[p1-1])
              p1 -= 1
              p2 -= 1 
          if c == 2:  # 根据标记，向左找下一个
              p2 -= 1
          if c == 3:   # 根据标记，向上找下一个
              p1 -= 1
  
      s.reverse() 
      return ''.join(s) 

• 该算法：

  • 时间复杂度 $O(MN)$
  • 空间复杂度 $O(MN)$

参考资料

• https://www.jianshu.com/p/a2cc662c0453

文章链接：
https://www.zywvvd.com/notes/study/algorithm/string/str-lcs/str-lcs/