你好！我是你的 OI 金牌教练。

这是一个非常深刻的问题，也是很多出题人在准备数据时会遇到的挑战。

为什么之前的暴力代码也 AC 了？

在随机数据下，两个碱基匹配的概率只有 $1/4$。暴力代码中的内层循环 for (int j = 0; j < m; ++j) 在遇到第 4 个错误时就会 break。在随机数据中，通常只需对比 5-8 个字符就会找齐 4 个错误。 因此，暴力的实际复杂度从理论的 $O(NM)$ 退化成了 $O(8N)$，这和 $O(N \log M)$ 在速度上几乎没有区别。

如何“卡掉”暴力？

我们要构造**“最坏情况” (Worst Case)：让主串和模式串极度相似**。 如果 $S_0$ 和 $S$ 全是字符 A，只有在 $S$ 的最后几个位置才出现错误。这样暴力算法的内层循环每次都要跑满 $M$ 次才能发现错误。

优化后的数据生成器 (针对性增强版)

这个生成器专门构造了“全 A 杀手”数据，能强制让暴力算法的运算量达到 $10^9$ 级别，从而实现真正的区分。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <chrono>
#include <algorithm>

using namespace std;

typedef unsigned long long ull;
const int MAXN = 200005;
const ull base = 131;

// --- 标准解法：用于生成 .out ---
ull h0[MAXN], hs[MAXN], p[MAXN];

ull get_h0(int l, int r) { return h0[r] - h0[l - 1] * p[r - l + 1]; }
ull get_hs(int l, int r) { return hs[r] - hs[l - 1] * p[r - l + 1]; }

int get_lcp(int p0, int ps, int n, int m) {
    int L = 1, R = min(n - p0 + 1, m - ps + 1);
    int res = 0;
    while (L <= R) {
        int mid = (L + R) >> 1;
        if (get_h0(p0, p0 + mid - 1) == get_hs(ps, ps + mid - 1)) { res = mid; L = mid + 1; }
        else R = mid - 1;
    }
    return res;
}

int solve_logic(string s0, string s) {
    int n = s0.length(), m = s.length();
    if (m > n) return 0;
    for (int i = 1; i <= n; ++i) h0[i] = h0[i - 1] * base + s0[i - 1];
    for (int i = 1; i <= m; ++i) hs[i] = hs[i - 1] * base + s[i - 1];
    p[0] = 1; for (int i = 1; i <= max(n, m); ++i) p[i] = p[i - 1] * base;
    int ans = 0;
    for (int i = 1; i <= n - m + 1; ++i) {
        int p0 = i, ps = 1, err = 0;
        while (ps <= m) {
            int lcp = get_lcp(p0, ps, n, m);
            p0 += lcp; ps += lcp;
            if (ps <= m) { if (++err > 3) break; p0++; ps++; }
        }
        if (err <= 3) ans++;
    }
    return ans;
}

// --- 构造工具 ---
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
char dna[] = {'A', 'T', 'C', 'G'};

void make_case(int id) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";
    ofstream fin(in_name);
    ofstream fout(out_name);

    if (id == 1) {
        fin << "1\nATCGCCCTA\nCTTCA\n";
        fout << "2\n";
    } else {
        int T = (id <= 6) ? 5 : 1;
        int N = (id <= 6) ? 5000 : 100000;
        int M = N / 2;
        fin << T << "\n";
        while (T--) {
            string s0, s;
            if (id >= 7) { 
                // --- 暴力杀手构造：全 A 数据 ---
                // 主串全 A，模式串前面全 A，最后 4 位是 T，逼迫暴力跑满 M 次
                s0 = string(N, 'A');
                s = string(M - 4, 'A') + "TTTT";
                // 随机扰动：在主串里埋几个符合条件的点，防止结果一直是 0
                for (int k = 0; k < 5; ++k) {
                    int pos = rng() % (N - M);
                    for (int j = 0; j < M; ++j) s0[pos + j] = s[j];
                }
            } else if (id >= 4) {
                // 中等规模相似数据
                s0 = string(N, 'G');
                s = string(M - 2, 'G') + "CC";
            } else {
                // 随机数据
                for (int i = 0; i < N; ++i) s0 += dna[rng() % 4];
                for (int i = 0; i < M; ++i) s += dna[rng() % 4];
            }
            fin << s0 << "\n" << s << "\n";
            fout << solve_logic(s0, s) << "\n";
        }
    }
    printf("Case %d [OK]\n", id);
}

int main() {
    for (int i = 1; i <= 10; ++i) make_case(i);
    return 0;
}

测试数据如何区分不同版本？

1. 对于暴力代码 (Brute Force)：

   • 在 Case 7-10 中，$N=10^5, M=5 \times 10^4$。
   • 由于 $S_0$ 和 $S$ 前面大部分都是 A，暴力代码的 for (int j = 0; j < m; ++j) 每一层几乎都要对比 $50,000$ 次才能发现第 4 个错误。
   • 总计算量：$10^5 \times 5 \times 10^4 = 5 \times 10^9$。
   • 结果：暴力算法在 1 秒内跑不完，必然 TLE。

2. 对于最优解 (Hash + Binary Search)：

   • 无论字符串长什么样，单次检查永远只需要 4 次二分查找。
   • 计算量：$10^5 \times 4 \times \log_2(50000) \approx 6.4 \times 10^6$。
   • 结果：即使在最坏情况下也只需 0.1s 左右，稳稳 AC。

读题关键词：隐藏的复杂度陷阱

• “连续子串匹配”：如果直接暴力，复杂度是 $O(NM)$。
• “允许修改 3 个”：这意味着如果用 LCP 跳跃，复杂度会降到 $O(NK \log M)$。
• “数据规模 $10^5$”：这是区分 $O(NM)$ 和 $O(N \log M)$ 的黄金分界线。

教练提示：在 OJ 出题时，构造特殊构造的单一字符数据是防止暴力程序“蒙混过关”的最有效手段。现在你可以重新生成数据，你的暴力代码在测试点 7-10 应该会变红（TLE）了！加油！

你好！我是你的 OI 金牌教练。

处理带容错的字符串匹配问题，核心矛盾在于如何快速跳过相同部分。这道题从暴力到最优解的进化过程，是典型的从“线性搜索”转向“对数级跳跃”的思维跨越。

第一阶段：朴素暴力 (Brute Force)

思路： 遍历 $S_0$ 中所有可能的起始位置。对于每个起点，逐字符与 $S$ 进行对比。如果遇到不匹配的字符，错误计数器 cnt 加 1。如果 cnt > 3，说明当前起点不合法，直接尝试下一个起点。

// 暴力版本 - 时间复杂度 O(T * N * M)
#include <iostream>
#include <string>
#include <vector>

using namespace std;

/**
 * P3763 [TJOI2017] DNA - 暴力尝试版本
 * 
 * 复杂度分析：
 * 时间复杂度：O(T * N * M)，其中 N 是 S0 长度，M 是 S 长度。
 * 在 N, M = 10^5 时，运算量过大，仅能通过 20% 的数据。
 * 空间复杂度：O(N + M)，用于存储字符串。
 */

void solve_brute() {
    string s0, s;
    // 读取 S0 和 S
    if (!(cin >> s0 >> s)) return;
    
    int n = s0.length();
    int m = s.length();
    int total_ans = 0;

    // 如果模式串比主串长，显然无法匹配
    if (m > n) {
        cout << 0 << endl;
        return;
    }

    // 枚举 S0 中每一个可能的起点 i
    for (int i = 0; i <= n - m; ++i) {
        int cnt = 0; // 记录当前子串与 S 的不同碱基数
        for (int j = 0; j < m; ++j) {
            if (s0[i + j] != s[j]) {
                cnt++;
                // 优化：一旦错误超过 3 个，立即跳出本层循环
                if (cnt > 3) break; 
            }
        }
        // 如果错误总数不超过 3，则该子串符合要求
        if (cnt <= 3) total_ans++;
    }
    
    // 输出结果
    cout << total_ans << endl;
}

int main() {
    // NOI 竞赛提速：关闭同步流
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    // 第一行读取测试组数 T
    if (cin >> t) {
        while (t--) {
            // 每组数据执行一次暴力逻辑
            solve_brute();
        }
    }
    
    return 0;
}

• 时间复杂度分析：$O(T \cdot N \cdot M)$。在 $10^5$ 规模下，计算量可达 $10^{11}$，由于数据组数 $T$ 的存在，必死无疑。
• 思考：我们大部分时间浪费在了重复对比那些本就相同的字符上。

第二阶段：最优复杂度 - 哈希+二分 (Hash & Binary Search)

思路升级： 我们只需要关心那 3个不匹配的位置。如果能瞬间“跳”过匹配的部分，速度将大幅提升。

1. 利用 字符串哈希 预处理 $S_0$ 和 $S$。
2. 对于某个起点 $i$，我们找它与 $S$ 的 LCP（最长公共前缀）。
3. 跳过 LCP 段，记录 1 次错误，然后从错误点后面继续找 LCP。
4. 因为只允许 3 次错误，所以一个起点最多只需要找 4 次 LCP。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 使用 unsigned long long 自然溢出取模，速度最快
typedef unsigned long long ull;
const int MAXN = 100005;
const ull base = 131; // 进制底数

ull h0[MAXN], h[MAXN], p[MAXN];
char s0[MAXN], s[MAXN];
int n, m;

// 获取 S0[l...r] 的哈希值 (1-indexed)
ull get_hash0(int l, int r) {
    return h0[r] - h0[l - 1] * p[r - l + 1];
}

// 获取 S[l...r] 的哈希值 (1-indexed)
ull get_hash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

// 二分查找 LCP 长度
int get_lcp(int p0, int ps) {
    int L = 1, R = min(n - p0 + 1, m - ps + 1);
    int res = 0;
    while (L <= R) {
        int mid = (L + R) >> 1;
        if (get_hash0(p0, p0 + mid - 1) == get_hash(ps, ps + mid - 1)) {
            res = mid;
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }
    return res;
}

void solve() {
    scanf("%s %s", s0 + 1, s + 1);
    n = string(s0 + 1).length();
    m = string(s + 1).length();

    // 预处理哈希前缀和
    p[0] = 1;
    for (int i = 1; i <= max(n, m); ++i) {
        h0[i] = h0[i - 1] * base + (s0[i] - 'A' + 1);
        h[i] = h[i - 1] * base + (s[i] - 'A' + 1);
        p[i] = p[i - 1] * base;
    }

    int total_ans = 0;
    for (int i = 1; i <= n - m + 1; ++i) {
        int pos0 = i, posS = 1, mistakes = 0;
        
        while (posS <= m) {
            int lcp = get_lcp(pos0, posS);
            pos0 += lcp;
            posS += lcp;
            
            if (posS <= m) { // 说明遇到了不匹配的字符
                mistakes++;
                if (mistakes > 3) break;
                pos0++; // 跳过这个错误字符
                posS++;
            }
        }
        if (mistakes <= 3) total_ans++;
    }
    printf("%d\n", total_ans);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

三、 复杂度分析思考过程

1. 朴素暴力：$O(T \cdot N \cdot M)$。
2. 哈希+二分：
   • 预处理：$O(N + M)$。
   • 单次检查：每个起点最多进行 4 次二分查找（因为错误数 $\le 3$），每次二分 $O(\log M)$。
   • 总复杂度：$O(T \cdot N \cdot 4 \cdot \log M)$。
   • 估算：$10 \cdot 10^5 \cdot 4 \cdot 17 \approx 6.8 \times 10^7$。这个量级在 1.0s 内可以通过，但需注意常数。

四、 时间复杂度优化建议

1. 自然溢出 vs 取模： 本代码使用 unsigned long long 自然溢出，这是哈希中最快的实现。但在高水平比赛中，如果怕被卡哈希，可以采用 双哈希（两组不同的模数），但这会使时间翻倍。
2. 后缀数组 (SA) / SAM： 如果这是一道求任意子串 LCP 的题，后缀数组可以在 $O(N)$ 预处理后 $O(1)$ 查询 LCP。
   • 优化后的复杂度：$O(T \cdot N \cdot 4)$。
   • 但在本题中，哈希+二分实现更简单，性价比极高。
3. Bitset 优化： 针对 DNA 只有 4 种碱基，可以用 std::bitset。记录 A, T, C, G 每个字符出现的位置集合，通过位移和位运算统计匹配数。复杂度 $O(T \cdot \frac{N \cdot M}{w})$，对于本题也是一个可行的备选方案。

五、 读题关键点总结

• “DNA 序列”：意味着字符集很小，哈希底数可以选得很小（如 5, 7, 131），且可能存在位运算优化的空间。
• “修改不超过 3 个”：核心词。看到这种极小的容错数，大脑要立刻反射出：“LCP 跳跃” 或 “搜索树剪枝”。
• “$10^5$”：排除了所有的 $O(N^2)$ 方案，引导你走向 $O(N \log N)$ 或 $O(N \sqrt{N})$。

教练点评： 这道题是“哈希二分求 LCP”套路的经典应用。在 NOIP/省选 级别，要熟练掌握这种将线性比较转化为对数跳跃的技巧。易错点在于二分的边界处理以及多组数据下数组的初始化（虽然本题覆盖写入即可）。祝你练习顺利！

你好！我是你的 OI 金牌教练。

今天我们分析的是 P3763 [TJOI2017] DNA。这道题在字符串匹配的基础上引入了“容错”机制，是考察 字符串哈希（String Hashing） 与 二分查找（Binary Search） 结合的经典进阶题，非常适合作为省选及 NOI 的练习。

一、 题目描述：P3763 [TJOI2017] DNA

【问题描述】 给定一段 DNA 碱基序列 $S_0$ 和一个目标基因序列 $S$。如果 $S_0$ 的某个连续子串与 $S$ 长度相同，且通过修改不超过 $3$ 个碱基（字母）就能变得与 $S$ 完全一致，则称该子串为“可能的基因”。 请统计 $S_0$ 中有多少个子串是“可能的基因”。

【输入格式】 第一行包含一个整数 $T$，表示数据组数。 对于每组数据： 第一行是一个长度不超过 $10^5$ 的字符串 $S_0$。 第二行是一个长度不超过 $10^5$ 的字符串 $S$。

【输出格式】 对于每组数据，输出一行一个整数，表示满足条件的连续子串个数。

【样例输入】

1
ATCGCCCTA
CTTCA

【样例输出】

2

【数据范围】

• 对于 20% 的数据：$|S_0|, |S| \le 10^4$。
• 对于 100% 的数据：$|S_0|, |S| \le 10^5$，$1 \le T \le 10$。
• 碱基序列仅包含 A, T, C, G 四种字符。

二、 预备知识点

1. 字符串哈希 (String Hashing)：用于 $O(1)$ 时间内判断两个子串是否相同。
2. 最长公共前缀 (LCP, Longest Common Prefix)：配合二分查找，在 $O(\log n)$ 时间内求出两个后缀的 LCP。
3. 贪心与“跳跃”思想：当允许 $k$ 次修改时，匹配过程变成了 $k+1$ 次“寻找匹配段 + 跳过不匹配点”的循环。
4. 前缀和 (Prefix Sum)：维护哈希值。

三、 教学启发与草稿纸推理

1. 启发式提问

• 教练问：如果我们直接枚举 $S_0$ 的每个起点进行暴力匹配，复杂度是多少？
• 学生答：$O(|S_0| \times |S|)$，在 $10^5$ 规模下会达到 $10^{10}$，显然会 TLE。
• 教练问：题目说只允许修改 3 个碱基。这意味着如果我们能瞬间跳过那些已经匹配的部分，只需要处理那 3 个“不匹配点”即可。怎么快速找到第一个不匹配的位置？
• 学生答：可以用哈希判断一段是否相等。第一个不相等的位置就是 LCP 的后一位。

2. 草稿纸模拟 (图形化逻辑)

假设我们要检查 $S_0$ 从 $i$ 开始的子串与 $S$ 是否匹配：

• 当前位置：$p_0$ (在 $S_0$ 中), $p$ (在 $S$ 中)，初始均为 0。
• 容错次数：mistakes = 0。
• 第一步：求出 $S_0[p_0 \dots]$ 与 $S[p \dots]$ 的 LCP 长度 $L$。
• 跳跃：直接将 $p_0$ 和 $p$ 向后移动 $L$ 位。此时 $S_0[p_0]$ 与 $S[p]$ 必定不同（或者已到末尾）。
• 记录错误：mistakes++，将指针跳过这个不匹配的字符（$p_0++, p++$）。
• 循环：重复上述过程直到 mistakes > 3 或匹配完成。

3. 复杂度分析与优化思考

• 二分+哈希求 LCP：单次复杂度 $O(\log |S|)$。
• 单次子串检查：最多进行 4 次 LCP 查找（对应 3 次容错 + 1 次收尾）。
• 总复杂度：$O(T \times |S_0| \times 4 \times \log |S|)$。
• 计算量：$10 \times 10^5 \times 4 \times 17 \approx 6.8 \times 10^7$。在 1.0s 内可以通过。
• 空间优化建议：预处理哈希幂次，使用 unsigned long long 自然溢出可以省去取模运算的常数。

四、 算法流程图 (Mermaid 语法)

graph TD
    Start("开始处理单组测试数据") --> PreHash("预处理 S0 和 S 的前缀哈希值")
    PreHash --> LoopSub("枚举 S0 中每个长度为 lenS 的子串起点 i")
    
    LoopSub -- "i 小于等于 n - m" --> InitCheck("初始化 pos0 = i, posS = 1, k = 0 (错误数)")
    LoopSub -- "遍历结束" --> Output("输出统计总数 Ans")
    
    InitCheck --> LCPCheck{"k 小于等于 3 且 posS 小于等于 m ?"}
    
    LCPCheck -- "是" --> BinarySearch("二分查找 S0+pos0 与 S+posS 的 LCP 长度 L")
    BinarySearch --> MovePos("pos0 += L, posS += L")
    MovePos --> EndOfStr{"posS 大于 m ?"}
    
    EndOfStr -- "是 (匹配完成)" --> AddAns("Ans 增加 1")
    EndOfStr -- "否 (遇到错误点)" --> IncK("k 增加 1, pos0 增加 1, posS 增加 1")
    IncK --> LCPCheck
    
    AddAns --> NextI("i 增加 1")
    LCPCheck -- "错误数 k 大于 3" --> NextI
    NextI --> LoopSub

五、 读题关键点总结

在 NOI 读题时，捕捉以下关键词以确定算法：

1. “等长连续子串”：说明是滑动窗口类匹配，固定长度。
2. “修改不超过 3 个”：
   • 这个 “3” 是极其关键的常数。
   • 如果这个数很大，可能需要动态规划或字符集统计；
   • 如果这个数很小（如 3），则强烈暗示可以利用 LCP 快速跳跃。
3. “长度 $10^5$”：
   • 排除 $O(N^2)$。
   • 目标复杂度应为 $O(N \log N)$ 或 $O(N \cdot K)$。
4. “DNA 序列 (A, T, C, G)”：
   • 字符集极小。在某些题中可能用到位运算优化（Bitset），但在本题哈希更通用。

教练寄语： 字符串哈希配合二分 LCP 是解决“带容错字符串匹配”的杀手锏。在编写时，注意哈希底数的选取（建议使用 $131$ 或 $13331$），并注意处理二分边界，确保 pos0 + L 和 posS + L 不会越界。祝你 AC！