采用KMP算法编程实现病毒感染检测算法

KMP（Knuth-Pratt）算法是一种用于字符串匹配的有效算法，尤其适合于查找文本串中是否存在某个模式串。在病毒感染检测中，可以将其应用来寻找特定病毒的特征序列是否出现在样本文件中。

编程实现KMP算法检测病毒感染的基本步骤如下：

1. **创建部分匹配表**（Partial Match Table，PMT）：对于模式串，构建一个PMT，它记录了在匹配失败时前缀和后缀相等的最大长度。这个表帮助我们在遇到不匹配字符时快速跳过部分已匹配的部分，避免无效的搜索。

2. **主循环**：遍历目标字符串，对于每个位置i，检查目标字符和模式串当前字符是否相等。如果相等，则递增指针；如果不等，利用PMT找到最长的非空公共前后缀，然后从模式串的第一个字符开始向右移动到这个公共前缀的结束位置继续比较。

3. **匹配结果**：如果匹配完成（即目标串的剩余部分为空），则表示找到了模式串；若遍历完目标串都没有找到匹配，说明没有感染迹象。

def build_PMT(pattern):
    PMT = [0] * len(pattern)
    j = -1
    for i in range(1, len(pattern)):
        while j != -1 and pattern[i] != pattern[j + 1]:
            j = PMT[j]
        if pattern[i] == pattern[j + 1]:
            j += 1
        PMT[i] = j
    return PMT

def KMP_search(text, pattern):
    PMT = build_PMT(pattern)
    i, j = 0, 0
    while i < len(text) and j < len(pattern):
        if text[i] == pattern[j]:
            i, j = i + 1, j + 1
        else:
            if j != 0:
                j = PMT[j - 1]
            else:
                i += 1
    return j == len(pattern)

# 示例
text = "这是一个测试样本，看看是否有病毒感染"
pattern = "病毒感染"
if KMP_search(text, pattern):
    print("存在病毒感染")
else:
    print("未发现病毒感染")