[面试手撕题]最长公共字串：[python][动态规划]

动态规划：

a, b = input(), input()
f = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]  # f[i][j] 以a[i]和b[j]结尾的共同子串长度
end, max_len = 0, 0

for i in range(len(a)):
    for j in range(len(b)):
        if a[i] == b[j]:
            f[i][j] = f[i - 1][j - 1] + 1
            if f[i][j] > max_len:
                max_len = f[i][j]
                end = i
print(max_len)
# print(a[end+1-max_len:end+1]) # 输出具体的串

简短一点就是：

a, b = input(), input()
f = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
max_len = 0

for i in range(len(a)):
    for j in range(len(b)):
        f[i+1][j+1] = f[i][j] + 1 if a[i] == b[j] else 0
        max_len = max(max_len, f[i+1][j+1])

print(max_len)

调整一下比对次数会更快：

a, b = input(), input()
f = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
max_len = 0

for i in range(len(a)):
    for j in range(len(b)):
        if a[i] == b[j]:
            f[i+1][j+1] = f[i][j] + 1
            max_len = max(max_len, f[i+1][j+1])

print(max_len)