蓝肽子序列 【决赛】(python)

从题目中可以看出本题要求的是最长蓝肽子公共子序列，我们都知道最长公共子序列是经典的动态规划算法，本题最长蓝肽子公共子序列经过一定的处理后可以转化为最长公共子序列问题。

s1 = input()
s2 = input()
def createDict(s):
    n = len(s)
    d = []
    start = 0
    for i in range(n):
        if i>0 and s[i] >= 'A' and s[i] <= 'Z' :
            d.append(s[start:i])
            start = i
    d.append(s[start:n])
    return d
d1 = createDict(s1)
d2 = createDict(s2)
# 最长公共子序列
n, m = len(d1), len(d2)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,m+1):
        if d1[i-1] == d2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[n][m])