题目理解

给定两个 DNA 序列 $S_0$ 和 $S$，DNA 序列只包含字符 A, T, C, G。

我们需要统计 $S_0$ 中有多少个长度与 $S$ 相同的连续子串，可以通过修改不超过 3 个字符变成 $S$。

换句话说，就是统计 $S_0$ 中与 $S$ 等长的子串，与 $S$ 的汉明距离 ≤ 3 的个数。

---

核心思路

1. 问题转化

设 $S_0$ 长度为 $n$，$S$ 长度为 $m$。

对于 $S_0$ 的每个起始位置 $i$（$1 \le i \le n-m+1$），考虑子串 $S_0[i \dots i+m-1]$ 与 $S[1 \dots m]$ 的匹配情况。

我们允许最多 $3$ 个位置不同，因此可以看作最多跳过 3 个不匹配的位置继续匹配。

---

2. 字符串哈希加速匹配

使用 滚动哈希（Rabin-Karp 哈希） 来快速比较两个子串是否相等。

定义哈希函数：

$$H(s) = \sum_{i=1}^{len} s[i] \cdot base^{len-i}$$

使用前缀哈希数组：

• $f[i]$ 表示 $S_0$ 前 $i$ 个字符的哈希值
• $g[i]$ 表示 $S$ 前 $i$ 个字符的哈希值

则子串 $S_0[l \dots r]$ 的哈希值为：

$$get\\_hash(l, r, f) = f[r] - f[l-1] \cdot p^{r-l+1} $$

其中 $p[k] = base^k$ 是预计算的幂。

---

3. 二分求最长公共前缀（LCP）

对于两个子串从某个位置开始，可以用二分 + 哈希快速求出它们的最长公共前缀。

uLL get_lcp(int l1, int l2, int r) {
    int l = 1, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (get_hash(l1, l1 + mid - 1, f) == get_hash(l2, l2 + mid - 1, g)) {
            l = mid + 1;
            ans = mid;
        } else
            r = mid - 1;
    }
    return ans;
}

---

4. 允许最多 3 次失配的匹配策略

对于每个起始位置 $i$，我们尝试匹配：

1. 找到第一个不匹配的位置（通过 LCP）
2. 跳过这个不匹配的位置（计为一次修改）
3. 继续匹配剩余部分
4. 重复以上过程，如果跳过次数 ≤ 3 就匹配成功

具体实现：

bool check(int l) {
    int r = l + lenb - 1, x = 1;  // x 是 S 中的当前位置
    
    for (int i = 0; i <= 3; i++) {  // 最多允许 3 次跳过
        if (x > lenb || get_hash(l, r, f) == get_hash(x, lenb, g))
            return 1;  // 匹配成功或剩余部分完全匹配
        
        int lcp = get_lcp(l, x, lenb - x + 1);  // 求最长公共前缀
        l += lcp + 1;  // 跳过匹配部分和第一个不匹配字符
        x += lcp + 1;
    }
    
    return 0;  // 超过 3 次跳过仍未匹配完
}

---

代码解析

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

typedef unsigned long long uLL;
const int maxn = 1e5 + 10;

char a[maxn], b[maxn];      // 存储字符串 S0 和 S
uLL p[maxn], f[maxn], g[maxn], base = 131;  // 哈希相关数组
int lena, lenb;             // 字符串长度

// 获取子串哈希值
uLL get_hash(int l, int r, uLL *h) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

// 二分求最长公共前缀长度
int get_lcp(int l1, int l2, int r) {
    int l = 1, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (get_hash(l1, l1 + mid - 1, f) == get_hash(l2, l2 + mid - 1, g)) {
            l = mid + 1;
            ans = mid;
        } else
            r = mid - 1;
    }
    return ans;
}

// 检查从位置 l 开始的子串是否能通过 ≤3 次修改匹配 S
bool check(int l) {
    int r = l + lenb - 1, x = 1;  // x 是 S 中的当前位置
    
    for (int i = 0; i <= 3; i++) {  // 最多允许 3 次跳过
        if (x > lenb || get_hash(l, r, f) == get_hash(x, lenb, g))
            return 1;  // 匹配成功或剩余部分完全匹配
        
        int lcp = get_lcp(l, x, lenb - x + 1);  // 求最长公共前缀
        l += lcp + 1;  // 跳过匹配部分和第一个不匹配字符
        x += lcp + 1;
    }
    
    return 0;  // 超过 3 次跳过仍未匹配完
}

void solve() {
    scanf("%s%s", a + 1, b + 1);
    lena = strlen(a + 1);
    lenb = strlen(b + 1);
    
    // 计算 S0 的前缀哈希
    for (int i = 1; i <= lena; i++)
        f[i] = f[i - 1] * base + a[i];
    
    // 计算 S 的前缀哈希  
    for (int i = 1; i <= lenb; i++)
        g[i] = g[i - 1] * base + b[i];
    
    int ans = 0;
    // 枚举所有可能的起始位置
    for (int i = 1; i <= lena - lenb + 1; i++) {
        if (check(i))
            ans++;
    }
    
    cout << ans << endl;
}

int main() {
    p[0] = 1;
    // 预计算 base 的幂次
    for (int i = 1; i <= maxn - 10; i++)
        p[i] = p[i - 1] * base;
    
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

---

复杂度分析

• 预处理：$O(n + m)$ 计算前缀哈希和幂次
• 每次检查：最多进行 $4$ 次 LCP 查询（对应最多 $3$ 次跳过）
• LCP 查询：每次 $O(\log m)$
• 总复杂度：$O(T \cdot (n + m + n \log m))$，在数据范围内可接受

---

算法优势

1. 避免暴力匹配：利用哈希快速判断子串相等
2. 二分加速：用 $O(\log m)$ 时间找到第一个不匹配位置
3. 灵活跳过：最多允许 $3$ 次不匹配，适应题目要求

这种方法比直接计算汉明距离更高效，特别适合允许少量错误的字符串匹配场景。