Cpp用矩阵和串写病毒匹配问题看人类是否感染

在C++中，我们可以利用矩阵和字符串数据结构来模拟病毒匹配的问题，比如经典的"Knuth-Morris-Pratt (KMP)"算法或者"Rabin-Karp"哈希算法，用于判断一个人是否感染了某种病毒。这个过程通常涉及到以下几个步骤：

1. **构建模式串**（病毒序列）：首先将病毒的DNA或RNA序列存储为一个字符串，例如 `std::string virus_seq`。

2. **创建最长公共前后缀数组（LCP）**：如果模式串中有重复的前缀，LCP可以帮助我们在遇到之前已匹配过的部分时快速跳过，减少不必要的比较。使用动态规划计算LCP数组。

3. **主循环**：对于每个潜在的感染点（人的DNA/RNA片段），从头开始和病毒模式串进行逐字符匹配。当匹配失败时，利用LCP数组指导回退，而不是直接跳到模式串的起始位置。

4. **匹配结果**：如果模式串完全匹配了某个人的部分序列，则表示这个人可能感染了病毒；如果没有匹配，继续扫描直到检查完整个序列。

#include <iostream>
#include <string>
using namespace std;

// LCP函数计算最长公共前后缀
int lcp(const string& pattern, int i, int j) {
    if (i == 0 || j == 0) return 0;
    while (pattern[i] == pattern[j]) {
        i--;
        j--;
    }
    return max(0, lcp(pattern, i+1, j+1));
}

bool isInfected(string sample, string virus_seq) {
    int n = sample.size();
    int m = virus_seq.size();
    vector<int> lcp_array(m);
    for (int i = 1; i < m; ++i) {
        lcp_array[i] = lcp(virus_seq, i, i - 1);
    }

    int index = 0;
    for (int i = 0; i <= n - m; ++i) {
        bool match = true;
        for (int j = 0; j < m && match; ++j) {
            if (sample[i + j] != virus_seq[j]) {
                // 如果当前字符不匹配，尝试回退并更新lcp_array
                if (j > lcp_array[j]) {
                    index += lcp_array[j];
                    j -= lcp_array[j]; // 跳过已经匹配的部分
                } else {
                    match = false;
                    break;
                }
            }
        }
        if (match) return true; // 发现匹配则认为可能感染
    }
    return false;
}

int main() {
    string sample, virus_seq;
    cin >> sample >> virus_seq;
    cout << (isInfected(sample, virus_seq) ? "可能感染" : "未感染") << endl;
    return 0;
}