C++ 算法解决基因序列匹配问题：寻找吃藕基因

加里敦大学的生物研究所发现了一个与人是否喜欢吃藕相关的基因序列 'S'。该研究表明，即使 'S' 序列中最多修改了 3 个碱基，仍然可以表现出吃藕的性状。现在，研究人员需要在 DNA 序列 '0S0' 中找到所有可能包含该基因的连续子串，即修改不超过 3 个字母就能变成 'S' 的 '0S0' 的连续子串。

输入格式

第一行是一个整数 'T'，表示数据组数。
每组数据的第一行是一个长度不超过 10^5 的碱基序列 '0S0'。
每组数据第二行是一个长度不超过 10^5 的吃藕基因序列 'S'。

输出格式

共 'T' 行，第 'i' 行表示第 'i' 组数据中，'0S0' 中有多少个与 'S' 等长的连续子串可能是吃藕性状的碱基序列。

样例

输入：

1 ATCGCCCTA CTTCA

输出：

算法

算法 1：暴力枚举

时间复杂度：O(Tn^2) (其中 n 是 'S' 的长度)

对于每个位置，暴力地考虑它到后面每个位置的子串是否与 'S' 相似即可。

算法 2：滑动窗口

时间复杂度：O(Tn)

对于每个位置 'i'，设 'j' 以 'i' 为起点，长度为 'S'。滑动窗口的同时维护两个哈希表，分别表示当前窗口与 'S' 的差别不超过 3 的位置集合，和超过 3 的位置集合。每次滑动窗口，如果新加入的位置与 'S' 的差别不超过 3，则把它加入差别不超过 3 的位置集合，否则加入超过 3 的位置集合。如果新加入的位置使得差别超过了 3，则需要把窗口左端点右移，同时把哈希表中对应的位置移除。

限制

20% 的数据，'0S0' 和 'S' 的长度不超过 10^4。
100% 的数据，'0S0' 和 'S' 的长度不超过 10^5，0 < T ≤ 10。

C++ 代码

// 算法 1：暴力枚举
#include <iostream>
#include <string>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        string s0, s;
        cin >> s0 >> s;
        int n = s.length();
        int cnt = 0;
        for (int i = 0; i <= s0.length() - n; ++i) {
            int diff = 0;
            for (int j = 0; j < n; ++j) {
                if (s0[i + j] != s[j]) {
                    ++diff;
                }
            }
            if (diff <= 3) {
                ++cnt;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

// 算法 2：滑动窗口
// (待补充)

参考文献

暂无