基于KMP算法的树种病毒检测

Question

任务描述
双生病毒是一类世界范围内广泛存在的单链环状DNA病毒，对多种植物造成毁灭性危害。近年来，随着技术的发展，研究人员不断从苹果、桑树等多种多年生树种中检测到新的双生病毒，并将其命名为苹果双生病毒（AGV）和桑花叶萎缩相关病毒（MMDaV）。
为了快速检测出树种是否感染某种双生病毒，将树种的DNA和病毒DNA均表示成由一些字母组成的字符串序列，然后检测某种双生病毒的DNA序列是否在该树种的DNA序列中出现过，如果出现过，则此树种感染了病毒，否则没有感染。注意，树种的DNA序列是线性的，而病毒的DNA序列是环状的。

请使用BM算法检测树种是否感染双生病毒，若感染，则输出“YES”，否则输出“No”。

编程要求
输入
多组数据，每组数据有一行，为序列A和B，A对应病毒的DNA序列，B对应树木的DNA序列。A和B都为“0”时输入结束。

输出
对于每组数据输出一行，若树木感染了病毒输出“YES”，否则输出“NO”。

测试说明
平台会对你编写的代码进行测试：

Answer 1

本答案参考 多次询问 ChatGPT-3.5 后选择的最佳回答，若是满意，还请采纳，谢谢

def kmp_table(pattern):
    length = len(pattern)
    table = [0] * length
    pos = 1
    cnd = 0
    while pos < length:
        if pattern[pos] == pattern[cnd]:
            cnd += 1
            table[pos] = cnd
            pos += 1
        elif cnd > 0:
            cnd = table[cnd - 1]
        else:
            table[pos] = 0
            pos += 1
    return table


def kmp_search(text, pattern):
    n = len(text)
    m = len(pattern)
    table = kmp_table(pattern)
    i = 0
    j = 0
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                return True
        elif j > 0:
            j = table[j - 1]
        else:
            i += 1
    return False


while True:
    inp = input().split()
    if inp[0] == '0' and inp[1] == '0':
        break
    virus = inp[0]
    tree = inp[1]
    found = False
    for i in range(len(virus)):
        new_virus = virus[i:] + virus[:i]
        if kmp_search(tree, new_virus):
            found = True
            break
    if found:
        print('YES')
    else:
        print('NO')