题解 | #查找两个字符串a,b中的最长公共子串#

计算复杂度O(n²)。

def a(b, c):
    m = len(b)
    num = 0
    num_max = 0
    pos = 0
    for i in range(0, m):
        if b[i] == c[i]:
            num += 1
        if b[i] != c[i]:
            if num > num_max:
                num_max = num
                pos = i-1
            num = 0
    if num > 0:
        if num > num_max:
            num_max = num
            pos = m - 1
    return pos - num_max + 1, num_max

str_1, str_2 = input(), input()
if len(str_1) < len(str_2):
    small = str_1
    long = str_2
else:
    small = str_2
    long = str_1

m = len(small)
n = len(long)

#n + m -1 -1
#0 <= i <= n + m - 2
num_max = 0
pos_first = m

for i in range(0, n+m-1):
    pos, num = a(small[0 if -(i+1) < -m else m-(i+1):m-i+n-1], long[0 if (i-m+1)<0 else (i-m+1):i+1])
    if num > 0:
        pos = (0 if -(i+1) < -m else m-(i+1)) + pos
        if num > num_max:
            num_max = num
            pos_first = pos
        elif num == num_max:
            if pos < pos_first:
                pos_first = pos

    #print(small[0 if -(i+1) < -m else m-(i+1):m-i+n-1])
    #print(long[0 if (i-m+1)<0 else (i-m+1):i+1])
print(small[pos_first : pos_first + num_max])