---

《ACM竞赛算法模板终极指南》

——从字符串匹配到数论密码，一键掌握夺冠必备工具库

---

一、为什么你需要这份模板？

ACM竞赛中，时间=生命！面对限时解题的高压场景，熟练调用经过验证的算法模板，能让你：

✅ 节省30%+编码时间（无需重复造轮子，直接套用优化过的逻辑）

✅ 减少90%+调试错误（模板经过竞赛级测试，边界条件处理完善）

✅ 快速定位问题核心（熟悉模板结构后，能更高效地分析题目与算法的匹配点）

本指南整合了字符串处理、数学问题、图论、几何等六大核心模块的经典算法模板，覆盖从入门到国赛级别的所有高频考点！

---

二、字符串处理模板：模式匹配与回文的核心武器

1. KMP算法（单模式串高效匹配）

用途：在目标字符串（n长）中查找模式串（m长）是否存在，时间复杂度 O(n+m)（远优于暴力O(n×m)）。

核心：通过next数组记录模式串的「最长相同前后缀」，失配时跳过无效比较。

# next数组生成（简化版）
def build_next(pattern):
    next = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = next[j-1]
        if pattern[i] == pattern[j]:
            j += 1
        next[i] = j
    return next

# 匹配逻辑
def kmp_search(text, pattern):
    next = build_next(pattern)
    j = 0
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = next[j-1]
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            return i - j + 1  # 匹配起始位置
    return -1

2. e-KMP（多模式串优化版）

升级点：针对多模式串匹配场景（如同时查多个关键词），通过扩展next数组逻辑，减少重复预处理开销。

3. Manacher算法（最长回文子串）

用途：在O(n)时间内找到字符串的最长回文子串（如「abba」的中心扩展优化）。

核心：利用对称性避免重复计算，通过维护「当前最右回文边界」加速扩展。

4. AC自动机（多模式串批量匹配）

用途：在一段文本中同时查找多个模式串的出现位置（如敏感词过滤）。

结构：基于Trie树构建状态机，通过失败指针（类似KMP的next）实现快速跳转。

5. 后缀数组 & 后缀自动机（高级字符串分析）

• 后缀数组：将字符串的所有后缀排序，用于解决最大重复子串、最长公共子串等问题。

• 后缀自动机：压缩状态的高效自动机，支持复杂子串查询（如不同子串数统计）。

6. 字符串Hash（快速比较）

用途：将字符串转换为整数哈希值，实现O(1)时间复杂度的子串对比（常用于判断两子串是否相等）。

常用哈希策略：多项式滚动哈希（如base^i * s[i]模大质数）。

---

三、数学问题模板：数论与组合的核心工具箱

1. 素数相关算法

• 素数筛选：埃拉托斯特尼筛法（O(n log log n)求≤n的所有素数）。

• 大区间素数筛选：分段筛法（解决POJ 2689等大范围素数问题）。

• Miller-Rabin随机素数测试：概率性判断大数是否为素数（适用于密码学场景）。

• Pollard-Rho因式分解：高效分解大整数的质因数（用于RSA相关问题）。

2. 模运算与逆元

• 扩展欧几里得算法：求解ax + by = gcd(a,b)，并计算模m下a的逆元（a*x ≡ 1 (mod m)）。

• 欧拉函数φ(n)：计算≤n且与n互质的数的个数（关键公式：φ(n)=n×∏(1-1/p)，p为n的质因数）。

• 中国剩余定理（CRT）：解模数互质的线性同余方程组（如「x≡a1(mod m1), x≡a2(mod m2)」）。

3. 组合数学公式

• 常见数列：斐波那契数（Fib）、卡特兰数（Catalan）、斯特林数（Stirling）、贝尔数（Bell）。

• 快速计算模板：预处理阶乘、逆阶乘，用费马小定理求组合数C(n,m) mod p。

4. 概率与随机化

• 随机素数测试：结合Miller-Rabin与大数分解，处理高精度数的质数判断。

---

四、扩展模板库：图论/几何/数据结构一键调用

1. 图论算法

• 最短路径：Dijkstra（单源非负权）、Bellman-Ford（含负权检测）、SPFA（队列优化）。

• 最小生成树：Kruskal（并查集+边排序）、Prim（贪心扩展）。

• 网络流：Dinic算法（最大流）、费用流（最小费用最大流）。

• 特殊图论问题：强连通分量（Kosaraju/Gabow）、二分图匹配（匈牙利算法/KM算法）。

2. 几何算法

• 基础计算：两点距离、三角形面积、圆心/内切圆半径计算。

• 高级问题：球面最短路径（大圆弧）、三维凸包、点线面位置关系判断。

3. 数据结构

• 树状数组/线段树：区间查询与单点更新（如求和、最值）。

• 并查集：动态连通性检测（带权/路径压缩优化）。

• 字典树（Trie）：字符串前缀统计与快速检索。

• 平衡树（Treap/Splay）：动态数据维护（如第K大查询）。

---

五、模板使用指南：从「背代码」到「懂逻辑」

1. 理解原理优先：不要直接复制代码！先弄懂算法的核心思想（如KMP的next数组本质是「失败跳转表」）。

2. 分类整理：按题目类型（如字符串题用KMP/AC自动机，数论题调素数筛+逆元模板）建立自己的「工具箱」。

3. 实战调试：在OJ平台上用经典题目测试模板（如用Manacher解「最长回文子串」，用Dinic解「最大流」）。

4. 优化适配：根据题目限制调整参数（如哈希模数选大质数防碰撞，素数筛范围按需缩小）。

---

六、暑期福利 & 下一步行动

🔥 限时优惠：购买ACM年卡会员，加赠3个月使用权+100次代码下载！

📚 推荐资源：

• 完整版Kuangbin ACM模板（覆盖几何/数论/图论全专题）

• 上海交大/浙大内部ACM模板（含STL优化与公式推导）

• 《ACM竞赛常用算法大全》Word版（附例题解析）

下一站预习：《数学模板深度解析：如何用欧拉函数+中国剩余定理秒杀组合题？》

思考题：当模板中的哈希函数发生冲突时（不同字符串哈希值相同），有哪些解决方案？（提示：双哈希/布隆过滤器）

（附：完整模板代码库已整理至ACM算法实验室GitHub（模拟链接），建议配合本指南分模块学习！）

现在开始，用模板武装你的竞赛之路——下一题，就是你的夺冠机会！ 💻🚀