最长公共子串 / 子序列

本文最后更新于:2022年7月12日 晚上

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

名词区别

  • 最长公共子串(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]$ 的最长公共子串的长度。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28

    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,否则为左方和上方的最大值。一个矩阵记录转移方向,然后根据转移方向,回溯找到最长子序列。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48

    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.zywvvd.com/notes/study/algorithm/string/str-lcs/str-lcs/
作者
Yiwei Zhang
发布于
2022年7月12日
许可协议