题目分析

题目给出两个字符串

要求我们输出两个字符串中的最长的公共子串的长度

方法一：暴力匹配

实现思路
- 从较短的字符串s1中暴力获取所有的子串
- 然后将每一个子串在s2中进行匹配，如果存在s2中而且长度比之前找到的公共子串更长，则更新mxlen
- 最终返回mxlen值

def solution(s1, s2):
    mxlen = 0
    if len(s1) > len(s2):
        s1, s2 = s2, s1            # s1为较短的字符串
    for i in range(len(s1)):
        for j in range(i, len(s1)):
            if s1[i:j+1] in s2 and j + 1 - i > mxlen:    # 从s1中截取所有的子串在s2中进行匹配，并更新最大值
                mxlen = j + 1 - i
    return mxlen

while True:
    try:
        s1 = input()
        s2 = input()
        print(solution(s1,s2))
    except:
        break;

复杂度分析

时间复杂度： $O (n^{4})$ ，我们为了分析代价方便，并便于和题目中要求的进阶代价进行比较考虑，不具体区分s1和s2长度的差异，统一用 $n$ 来表示，这样对应的时间代价为4次方的代价。由于暴力截取s1的双重循环代价为 $O (n^{2})$ ，然后在s2中搜索s1进行匹配所用的in操作带来的时间开销也是 $O (n^{2})$ ，因此总共代价为4次方 $O (n^{4})$
空间复杂度： $O (1)$ ，未引入额外的空间代价

方法二：动态规划

实现思路
- 我们定义dp[i][j]的含义为在s1，s2中分别以s1[i-1],s2[j-1]为结尾的两个公共子串的长度。当dp[i][j]=0时说明s1[i-1] != s2[j-1]
- 然后遍历两个字符串，指针分别为i和j，当出现s1[i] == s2[j]的时候，则说明需要更新dp[i+1][j+1] = 1 + dp[i][j]
- 因此我们有转移方程
$dp[i+1][j+1] = 1 + dp[i][j]\;\;\;\;\;if (s1[i] == s2[j])$
- 最终返回记录的dp数组中最大值即可

alt


def solution(s1, s2):
    mxlen = 0
    dp = [[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)]    # 动态规划数组
    for i in range(len(s1)):
        for j in range(len(s2)):                # 想要找到两个字符串中相同的字母，然后看看以这公共字母结尾的子串是否能进行长度拓展
            if s1[i] == s2[j]:
                dp[i+1][j+1] = dp[i][j] + 1     # 更新最长子串的值
                if dp[i+1][j+1] > mxlen:
                    mxlen = dp[i+1][j+1]
    return mxlen

while True:
    try:
        s1 = input()
        s2 = input()
        print(solution(s1,s2))
    except:
        break;

复杂度分析

时间复杂度： $O (n^{2})$ ，同样我们以代价来看，不具体区分s1和s2长度差异，则可以得到时间开销关键在于双重循环遍历s1和s2上。
空间复杂度： $O (n^{2})$ ，dp数组的空间开销

题解 | #公共子串计算#

题目分析

方法一：暴力匹配

复杂度分析

方法二：动态规划

复杂度分析