潍坊网站排名优化,网站seo优化技术入门,链接搜索引擎,百度关键字排名软件人的DNA和病毒DNA均表示成由一些字母组成的字符串序列。然后检测某种病毒DNA序列是否在患者的DNA序列中出现过#xff0c;如果出现过#xff0c;则此人感染了该病毒#xff0c;否则没有感染。例如#xff0c;假设病毒的DNA序列为baa#xff0c;患者1的DNA序列为aaabbba如果出现过则此人感染了该病毒否则没有感染。例如假设病毒的DNA序列为baa患者1的DNA序列为aaabbba则感染患者2的DNA序列为babbba则未感染。注意人的DNA序列是线性的而病毒的DNA序列是环状的)
输入格式:
输入第一行中给出1个整数i(1≤i≤11)表示待检测的病毒DNA和患者DNA的对数。 输入i行串序列每行由两个字符串组成字符串中不含不可见字符两字符串之间用一个空格分隔分别代表病毒的DNA序列和患者的DNA序列病毒的DNA序列和患者的DNA序列长度不超过500。
输出格式:
依次逐行输出每对检测样本的结果感染输出YES未感染输出NO。
输入样例1:
1
baa bbaabbba输出样例1:
YES输入样例2:
2
cced cdccdcce
bcd aabccdxdxbxa输出样例2:
YES
NO
分析
index函数这个函数的目的是检查DNA序列s中是否存在病毒序列t。它通过同时遍历两个序列当字符匹配时两个指针都向前移动。如果不匹配则将DNA序列的指针向前移动并将病毒序列的指针重置为0。如果在遍历完整个DNA序列后病毒序列也完全遍历了那么就返回True表示DNA中存在该病毒。trans函数这个函数的目的是转换病毒序列。它接收一个字符串复制第一个字符然后将其余字符复制到字符串的开头。例如ABC经过转换后会变成BCA。这个转换的目的是为了扩大病毒序列的字典序范围从而更全面地检查DNA序列。test函数这个函数对DNA序列进行多次转换后的所有可能版本进行检查看是否存在与病毒序列匹配的子序列。它通过调用index函数来实现。如果在所有转换后的版本中都没有找到匹配的子序列那么就返回False表示DNA中不存在该病毒。最后代码读取输入数据对每个测试用例进行测试。每个测试用例包括病毒序列和DNA序列然后根据test函数的返回结果输出YES或NO。
Python版本
def index(s, t):i, j 0, 0while i len(s) and j len(t):if s[i] t[j]:i 1j 1else:i i - j 1j 0if j len(t):return Trueelse:return Falsedef trans(t):a tb a[0]t a[1:] breturn tdef test(s, t):for i in range(len(t)):if i ! 0:t trans(t)if index(s, t):return Truereturn Falsen int(input())
for _ in range(n):virus, DNA input().split()if test(DNA, virus):print(YES)else:print(NO)总结 这个算法的思路是利用滑动窗口和字符匹配来找出是否存在特定的病毒序列。通过转换病毒序列并多次检查其所有可能版本可以更全面地检查DNA序列。
