DNA序列

"""
真分数:y/x<(y+1)/(x+1)
dp[i][j]：S[i]~S[j]构成子列的GC个数
"""
while True:
    try:
        S=input()
        N=int(input())
        n=len(S)
        dp=[[0]*n for _ in range(n)]
        max_ration=0
        # 初始化
        for i in range(n):
            if S[i] in 'CG':
                dp[i][i]=1  
            
        for i in range(n):
            for j in range(i+1,n,1):
                if S[j] in 'GC':
                    dp[i][j]=dp[i][j-1]+1
                if S[j] not in 'GC':
                    dp[i][j]=dp[i][j-1]
        for j in range(1,n,1):
            for i in range(0,j,1):
                if S[i] in 'GC':
                    dp[i][j]=dp[i+1][j]+1
                if S[i] not in 'GC':
                    dp[i][j]=dp[i+1][j]
        
        if n>N:
            for i in range(n-N):
                j=i+N-1
                tmp=dp[i][j]
                if tmp>max_ration:
                    max_ration=tmp
            for i in range(n-N):
                j=i+N-1
                if dp[i][j]==max_ration:
                    print(S[i:j+1])   
                    break    
        else:
            print(S)
    except:
        break

s = input() 
n = int(input())
res = list() 

for i in range(len(s)-n+1):
    res.append(s[i:i+n])

res.sort(key=lambda x:(x.count('C')+x.count('G'))/n,reverse=True) 

print(res[0])

a = input()
k = int(input())
n = len(a)
ratio = 0
result = ""
for i in range(0,n-k+1):
    temp = a[i:i+k]
    new_ratio = (temp.count("G") + temp.count("C"))/k
    if new_ratio > ratio:
        ratio = new_ratio
        result = temp
print(result)

# 窗口滑动问题
while True:
    try:
        DNA = input()
        num = int(input())
        i = 0
        max_CG = 0
        res = ''
        
        # 避免固定长度与给定字符串相同的情况，要加到最后一位
        while i <= len(DNA) - num:
            if DNA[i:i + num].count('C') + DNA[i:i + num].count('G') > max_CG:
                max_CG = DNA[i:i + num].count('C') + DNA[i:i + num].count('G')
                res = DNA[i: i + num]
                i += 1
            else:
                i += 1

        print(res)

    except:
        break

n=input()
m=int(input())
dic={}
l=0
if len(n)==m:
    print(n)
else:
    for i in range(len(n)-m):
        a=n[i:i+m].count('C')
        b=n[i:i+m].count('G')
        dic[n[i:i+m]]=a+b
        if a+b>l:
            l=a+b
    for i in dic:
        if dic[i]==l:
            print(i)
            break

dna = input()
length = int(input())

if length >= len(dna):
    print(dna)
else:
    sub_strs = []
    for index in range(len(dna)-length):
        sub_strs.append(dna[index:index+length])

    GC_ratio = []
    for sub_str in sub_strs:
        GC_ratio.append((sub_str.count("C") + sub_str.count("G"))/length)

    highest_GC_ratio_index = GC_ratio.index(max(GC_ratio))
    print(sub_strs[highest_GC_ratio_index])

while True:
    try:
        DNA=input()
        n=int(input())
        Max=0
        dp=[]
        if len(DNA)==n:
            print(DNA)
            break
        for i in range(0,len(DNA)-n):
            c_count=DNA[i:i+n].count("C")
            G_count=DNA[i:i+n].count("G")
            if (c_count+G_count)>Max:
                Max=(c_count+G_count)
                dp.append(DNA[i:i+n])
        for i in dp:
            if (i.count("C")+i.count("G"))==Max:
                print(i)
                break
    except:
        break

while True:
    try:
        strs = input()
        l = int(input())
        a = []
        k = 0     #比例系数
        for i in range(len(strs)):     
            a.append(strs[i:i+l])    #所有子串依次放入列表
            if k < (strs[i:i+l].count("C") + strs[i:i+l].count("G")): #判断每个子串中的CG个数
                k = strs[i:i+l].count("C") + strs[i:i+l].count("G")   #保留最大个数
        for i in a:
            if (i.count("C")+i.count("G")) == k:    #二次遍历，第一次出现最大个数，立即输出该子串
                print(i)
                break    #仅输出一次       
    except:
        break

while True:
    try:
        DNA = input()
        n = int(input())
        max_per = 0
        for i in range(len(DNA)-n+1):
            a = DNA[i:i+n]
            new_per = (a.count('C') + a.count('G')) / n
            if new_per > max_per:
                max_per = new_per
        for i in range(len(DNA)-n+1):
            if (DNA[i:i+n].count('C') + DNA[i:i+n].count('G')) / n == max_per:
                print(DNA[i:i+n])
                break
    except:
        break

while True:
    try:
        a = input('')
        N = int(input(''))
        res = ''
        num = 0 # 记录先遇到的GC含量最大的子串长度
        for i in range(len(a)-N+1):
            if a[i:i+N].count('C')+a[i:i+N].count('G') > num:
                num = a[i:i+N].count('C')+a[i:i+N].count('G')
                res = a[i:i+N]
        print(res)
    except:
        break