最长的公共连续子串

一、题目描述

两个字符串（可能包含空格）,找出其中最长的公共连续子串, 并输出其长度。

二、解题思路 & 代码

2.1 动态规划（二维）

创建一个二维数组 $d p [n] [m]$ ，

其中 $d p [i] [j]$ : 表示取到 $s 1 [i]$ 和取到 $s 2 [j]$ 时的最大连续子串长度。

如果 $s 1 [i]$ 等于 $s 2 [j]$ ，则 $d p [i] [j]$ 等于取到 $s 1 [i - 1]$ 和取到 $s 2 [j - 1]$ 时的最大连续子串长度加 $1$ ，即 :
$d p [i] [j] = d p [i - 1] [j - 1] + 1$

import sys

def maxSubStr(s1, s2):
    n1 = len(s1)
    n2 = len(s2)
    maxLen = 0
    maxEnd_1 = 0
    maxEnd_2 = 0
    dp = [[0] * n2 for i in range(n1)]
    for i in range(n1):
        for j in range(n2):
            if s1[i] == s2[j]:
                if (i == 0 or j == 0):
                    dp[i][j] = 1
                else:
                    dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = 0
			
			# 为了后续取出子串
            if dp[i][j] > maxLen:
                maxLen = dp[i][j]
                maxEnd_1 = i      # 字符串 s1 的终点位置
                maxEnd_2 = j      # 字符串 s2 的终点位置

    return maxLen, s1[maxEnd_1 - maxLen + 1: maxEnd_1+1], s2[maxEnd_2 - maxLen + 1: maxEnd_2+1]


if __name__ == '__main__':
    s1 = 's wwABC2AsssssABCA'
    s2 = 'wqABC2A'
    # s1 = sys.stdin.readline().strip()
    # s2 = sys.stdin.readline().strip()
    res = maxSubStr(s1, s2)
    print(res)

输出：
（长度，从 s1 中截取的，从 s2 中截取的）

(5, 'ABC2A', 'ABC2A')

时间复杂度： $O (M N)$ ，M、N 分别为两个字符串的长度
空间复杂度： $O (M N)$

2.2 动态规划（ $O (1)$ ）

优化： 每次计算 $d p [i] [j]$ 的时候，最多只需要其左上方的 $d p [i - 1] [j - 1]$ 的值，所以按照斜线方向（自左上角至右下角方向）来计算所有的值

def maxSubStr_2(s1, s2):
    n1 = len(s1)
    n2 = len(s2)
    row = 0       # 斜线开始位置的行
    col = n2 - 1  # 斜线开始位置的列
    maxLen = 0    # 最大长度
    end = 0       # 子串的结尾位置索引
    while row < n1:
        i = row
        j = col
        curLen = 0
        while i < n1 and j < n2:  # 从 (i, j) 开始向右下方遍历
            if s1[i] != s2[j]:
                curLen = 0
            else:
                curLen += 1
                
            if curLen > maxLen:   # 记录最大值，以及结束字符的位置索引
                end = i
                maxLen = curLen
            i += 1
            j += 1
        if col > 0:            # 斜线开始位置的列先向左移动
            col -= 1
        else:                  # 列移动到最左之后，行向下移动
            row += 1

    return maxLen, s1[end - maxLen + 1: end + 1]


if __name__ == '__main__':
    s1 = 's wwABsedC2AsssssABCA'
    s2 = 'wqABesdC2A'
    # s2 = 'dddd'
    res2 = maxSubStr_2(s1, s2)
    print("res2:", res2)

输出：

res2: (4, 'dC2A')

时间复杂度： $O (M N)$ ，M、N 分别为两个字符串的长度
空间复杂度： $O (1)$

参考：

动态规划-----最长公共连续子串

最长的公共连续子串

一、题目描述

二、解题思路 & 代码

2.1 动态规划（二维）

2.2 动态规划（ O ( 1 ) O(1) O(1) ）

参考：

2.2 动态规划（ $O (1)$ ）