病毒感染监测kmp算法c++

KMP（Knuth-Pratt）算法是一种字符串匹配算法，特别适合于检测文本中是否存在某个模式串。在病毒感染监测的场景中，它可以用于快速查找病毒的特征序列是否存在于样本文件中。

在C++中实现KMP算法的基本步骤包括以下几个部分：

1. **构造失配函数** (Partial Match Table, PMT)：通过预处理模式串，计算出当模式串发生前缀和自身不匹配时需要跳过的字符数。这一步减少了模式串中不必要的搜索。

vector<int> computePMT(const string& pattern) {
    int len = pattern.length();
    vector<int> pm(len, 0);
    for(int i=1; i<len; ++i) {
        while(pmt[i-1] != 0 && pattern[pmt[i-1]] != pattern[i]) {
            pm[i] = pmt[i-1];
        }
        if(pattern[pmt[i-1]] == pattern[i]) {
            pm[i]++;
        }
    }
    return pm;
}

2. **实际匹配过程**：使用`pmt[]`数组，在主串中从头开始搜索，遇到不匹配时根据`pmt`更新搜索位置。

bool kmpMatch(string text, const string& pattern) {
    int text_len = text.length(), pattern_len = pattern.length();
    vector<int> pm = computePMT(pattern);

    int j = 0;
    for(int i=0; i<text_len; ++i) {
        if(i < pattern_len && text[i] == pattern[j]) {
            j++;
        } else if(j > 0) {
            j = pm[j-1];
        } else {
            // 没有找到匹配，继续下一个字符
            continue;
        }
        if(j == pattern_len) { 
            return true; // 找到了匹配
        }
    }
    return false;
}