牛客华为HJ75公共子串计算

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 非常典型的滑动窗口题目。
# 在长串 上有一个游走的虚拟 窗口，将窗口内的内容和 短的串比较，看看有多少个重复元素。
# 窗口的 左边索引是l ，右边索引是r。
# 但是我自己动手写了一遍，发现滑动窗口的写法并不好写。于是换动态规划来写。
# 换动态规划：
# 设定 d[i][j] 为 a[i-1] b[j-1] 结尾的字符串的公共子串长度；
# 则 d[i][j] 在 a[i-1] == b[j-1] 情况下，需要更新 为 d[i][j] = d[i-1][j-1] + 1
# 这种在 某种情况下更新的 递推公式，往往最大值不会出现在最后，需要max求结果。

a,b = input(),input()
d = [[ 0 for j in range(len(b)+1)] for i in range(len(a)+1)] # 初始化 
result = [0]
for i in range(1,len(a)+1):
    for j in range(1,len(b)+1):
        if a[i-1] == b[j-1]:
            d[i][j] = d[i-1][j-1] + 1
            result.append(d[i][j])
print(max(result))