题目分析

1. 题目给出两个字符串
2. 要求我们输出两个字符串中的最长的公共子串的长度

方法一：暴力匹配

• 实现思路
  • 从较短的字符串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)O(n^4)$，我们为了分析代价方便，并便于和题目中要求的进阶代价进行比较考虑，不具体区分s1和s2长度的差异，统一用$nn$来表示，这样对应的时间代价为4次方的代价。由于暴力截取s1的双重循环代价为$O(n^2)O(n^2)$，然后在s2中搜索s1进行匹配所用的in操作带来的时间开销也是$O(n^2)O(n^2)$，因此总共代价为4次方$O(n^4)O(n^4)$
• 空间复杂度：$O(1)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[i+1][j+1]\; =\; 1\; +\; dp[i][j]\backslash ;\backslash ;\backslash ;\backslash ;\backslash ;if\; (s1[i]\; ==\; s2[j])$
  • 最终返回记录的dp数组中最大值即可

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