python-蓝肽子序列

解题思路:

这道题和寻找两个字符串之间最长的公共子序列的做法是完全一样的。不同的就是此处的蓝肽并不是字母，我们把它看作字母来做就好了。

在进行查找之前，我们要对蓝肽蛋白质进行处理，也就是将蓝肽蛋白质中的蓝肽分开。

通过分析蓝肽的特点，每个蓝肽的首字母是大写的，之后的为小写。

那么我们可以先将蓝肽蛋白质中每个大写字母的下标给记录下来存放到一个数组中，再数组最后要再添加一下蓝肽蛋白质的长度。

举个例子：

假设蓝肽蛋白质s为：LanTaiXiaoQiao

存放每个大写字母下标的数组记为S_Up，则S_Up = [0,3,6,10,14]

那么蓝肽蛋白质中的所有蓝肽就是s[0:3]，s[3:6]，s[6:10]，s[10:14]

接下来我们按照寻找两个字符串之间最长的公共子序列的做法去做就好了。

建立一个大小为(n*m)二位数组dp，其中dp[i][j]代表当s取到i，t取到j时两者的最长公共子串的长度

如果s[i] == t[j]

则dp[i][j] = dp[i-1][j-1]

如果s[i] != t[j]

则dp[i][j] = max(dp[i][j-1],dp[i-1][j])

最后输出dp[n-1][m-1]即可得到答案

注意事项:

参考代码:

def f(s,t):  
    S = [0]            #存放s划分后的蓝肽  
    S_Up = []          #记录s中大写字母的下标  
    T = [0]            #存放s划分后的蓝肽  
    T_Up = []          #记录t中大写字母的下标  
    for i in range(len(s)):  
        if 'A' <= s[i] <= 'Z':  
            S_Up.append(i)  
    S_Up.append(len(s))   #此处要在最后再添加一个s的长度，以便后面划分字符串  
      
    for i in range(len(t)):  
        if 'A' <= t[i] <= 'Z':  
            T_Up.append(i)  
    T_Up.append(len(t))   #此处要在最后再添加一个t的长度，以便后面划分字符串  
  
    for i in range(len(S_Up)-1):  #对s划分蓝肽  
        l = S_Up[i]  
        r = S_Up[i+1]  
        S.append(s[l:r])  
  
    for i in range(len(T_Up)-1):  #对t划分蓝肽  
        l = T_Up[i]  
        r = T_Up[i+1]  
        T.append(t[l:r])  
  
    n = len(S)  
    m = len(T)  
    dp = [[0 for j in range(m)] for i in range(n)]    #查找最长子序列  
    for i in range(1,n):  
        for j in range(1,m):  
            if S[i] == T[j]:  
                dp[i][j] = dp[i-1][j-1]+1  
            else:  
                dp[i][j] = max(dp[i][j-1],dp[i-1][j])  
  
    print(dp[n-1][m-1])  
      
  
if __name__ == '__main__':  
    s = input().strip()  
    t = input().strip()  
    f(s,t)