题目分析

1. 题目给出我们两个字符串
2. 我们需要返回两个字符串的最长公共子串，注意不是子序列

方法一：以长度拓展

• 实现思路

  • 我们对于一个短一点的字符串s1进行子串截取

  • 我们期待找到一个公共子串，该公共子串的长度为l，l从1到len(s1)遍历

  • 在s1中我们将这个子串提取出来，到s2中进行匹配

  • 如果子串在s2中匹配成功，并且比之前找到的子串长度还要长，则确定当前这个子串为结果，否则之前的子串是结果

  • 最终返回找到的最长公共子串

def solution(s1, s2):
    if len(s1) > len(s2):                        # 较短的字符串用s1表示
        s1, s2 = s2, s1
    mxlen = 0
    for l in range(1, len(s1)):                  # 规定一个子串长度，找找s1和s2中是否有符合的相同子串
        for i in range(0, len(s1)-l+1):          # 遍历s1子串起点进行尝试
            sub = s1[i:i+l]                      # 切分子串
            if sub in s2 and l > mxlen:          # 搜索是否存在且是否需要更新
                mxlen = l
                res = sub
    print(res)
    
    return

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

复杂度分析

• 时间复杂度：$O(m{n}^2)O(mn^2)$，其中s1长为m，s2长为n，代码中可见的部分有双重循环，在in方法中又又$O(n)O(n)$的时间代价，总计$O(n^3)O(n^3)$时间代价
• 空间复杂度：$O(1)O(1)$，只引入了一些变量级别的常数空间开销

方法二：双指针+剪枝

• 实现思路
  • 我们这次通过先确定一个子串首，再遍历确定子串尾的方式进行切分
  • 切分完成后将这个子串在s2中进行查找，如果找到公共子串，则判断是否当前的更长，如果更长则计入mxlen中，并且更新结果子串
  • 如果我们已经确定了一定长度的子串，则我们之后在双指针确定子串首尾的时候直接在这个长度基础上寻找，因此我们甚至不用判断 j - i > mxlen 这一步骤

def solution(s1, s2):
    if len(s1) > len(s2):                        # 较短的字符串用s1表示
        s1, s2 = s2, s1
    mxlen = 0
    for i in range(len(s1)):                     # 找一个子串起点
        for j in range(i+1+mxlen, len(s1) + 1):  # 找一个子串终点
            sub = s1[i:j]                        # 截取子串
            if sub in s2 :                       # 子串是否在s2中
                res = sub
                mxlen = j - i
                continue
    print(res)
    
    return

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

复杂度分析

• 时间复杂度：$O(m{n}^2)O(mn^2)$，虽然最差结果时间代价还是三次方，但是中间过程可以省去很多不必要的遍历和查找
• 空间复杂度：$O(1)O(1)$，只引入了一些变量级别的常数空间开销