字符串哈希与KMP周期性定理的高效应用

核心逻辑与数学原理

在 NOIP 级别的字符串测试中，当面临极高的数据规模或多维度的子串判定时，单靠 KMP 往往会受限于单指针匹配的拓扑单一性。本节将拆解两大竞赛级破局利器：多进制大素数 Hash 的抗碰撞设计与 KMP 前缀函数的周期性定理。

1. 字符串 Hash 的双模数抗碰撞设计

字符串 Hash 的本质是将任意长度的字符串映射为固定大小的整型数字。设字符串 $S = s_1s_2\dots s_n$，选择一个固定基数 $Base$（通常选用大质数，如 $131$ 或 $13331$）以及模数 $M$。其单哈希值递推公式为：

$$H[i] = (H[i-1] \times Base + s_i) \pmod M$$

由此，任意子串 $S[l \dots r]$ 的 Hash 值可在 $O(1)$ 时间内由前缀和差分式公式切出：

$$Hash(S[l \dots r]) = (H[r] - H[l-1] \times Base^{r-l+1}) \pmod M$$

生日攻击与哈希碰撞定理：根据生日悖论，在 $O(\sqrt{M})$ 个不同字符串中，发生哈希碰撞（即两个不同字符串具有相同哈希值）的概率将极速逼近 $1$。如果选用单 unsigned long long 自然溢出（相当于 $M = 2^{64}$），或者选用单质数 $10^9+7$，由于竞赛测例中常常存在故意构造的“卡自然溢出”恶性数据（如抗溢出黑客滑块机制），极易引发数据碰撞导致 WA。

双 Hash 设计：选取两组完全独立的基数与大质数对 $(Base_1, M_1)$ 和 $(Base_2, M_2)$，每个字符串用一个二元组 $(Hash_1, Hash_2)$ 唯一标记。有效的抗碰撞模数通常从以下工业级大素数中选取：

$M_1 = 1000000007 \quad (10^9+7)$
$M_2 = 1000000009 \quad (10^9+9)$
$M_3 = 998244353$

2. KMP 前缀函数的周期性定理（最小循环节定理）

前缀函数 $next$（或称前缀函数 $\pi$）不仅可以用于匹配，其内部封存了强烈的局部拓扑周期性特征。

周期性定理：设一个字符串的长度为 $N$，其前缀函数末尾位置的值为 $next[N-1]$（0-based 下对应整个串的最长相等前后缀长度）。令 $L = N - next[N-1]$。

若 $N \pmod L == 0$，则 $L$ 严格为该字符串的最小正周期（最小循环节长度），该串由长度为 $L$ 的子串连续复制 $\frac{N}{L}$ 次构成。
若 $N \pmod L \neq 0$，则该串在全局不具备完美的整周期性，但 $L$ 依然代表其排除了多余残缺后缀后的最小可能潜在周期。

证明：已知长度为 $next[N-1]$ 的前缀与后缀完全相同。这意味着对原串进行向右平移 $L = N - next[N-1]$ 位后，平移部分的重叠区域完全错位对齐。若 $N$ 能被 $L$ 整除，说明错位滑块刚好无缝拼接了整段序列，定理成立。

状态设计与算法推导

1. 双 Hash 前缀和差分状态

H1[i], H2[i]：分别记录字符串前 $i$ 个字符在双模数系统下的哈希前缀和。
P1[i], P2[i]：预处理出的 $Base_1^i \pmod {M_1}$ 和 $Base_2^i \pmod {M_2}$ 幂次表，用作差分对齐时的乘法算子。

2. 任意子串哈希抽取推导

抽取 $S[l \dots r]$（下标从 1 开始）的双哈希特征值：

$$ans_1 = (H1[r] - H1[l-1] \times P1[r-l+1]) \pmod {M_1}$$

$$ans_2 = (H2[r] - H2[l-1] \times P2[r-l+1]) \pmod {M_2}$$

若运算结果为负数，需强行执行补码修正：$ans = (ans + M) \pmod M$。

C++ 标准源码（NOIP风格）

下面提供一套融合了“双哈希子串精确判定”与“KMP周期性秒杀”的高阶工业源码。

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

using namespace std;

const int MAXN = 1000005;

// 双 Hash 参数设计：严格选用两套不同的大素数与基数
const long long BASE1 = 131;
const long long MOD1 = 1000000007;
const long long BASE2 = 13331;
const long long MOD2 = 1000000009;

long long h1[MAXN], p1[MAXN];
long long h2[MAXN], p2[MAXN];
int nxt[MAXN];

// ================== CORE 1: 双 Hash 系统预处理与局部抽取 ==================
void init_hash(const string& s, int n) {
    p1[0] = 1; p2[0] = 1;
    h1[0] = 0; h2[0] = 0;

    for (int i = 1; i <= n; ++i) {
        p1[i] = (p1[i - 1] * BASE1) % MOD1;
        p2[i] = (p2[i - 1] * BASE2) % MOD2;

        // s[i-1] 是因为 C++ string 0-based 下标映射
        h1[i] = (h1[i - 1] * BASE1 + s[i - 1]) % MOD1;
        h2[i] = (h2[i - 1] * BASE2 + s[i - 1]) % MOD2;
    }
}

// 抽取 1-based 下标区间 [l, r] 的双哈希特征值，打包为 pair 返回
pair<long long, long long> get_sub_hash(int l, int r) {
    long long res1 = (h1[r] - h1[l - 1] * p1[r - l + 1]) % MOD1;
    if (res1 < 0) res1 += MOD1; // 致命踩坑点：C++ 取模负数必须手动补正

    long long res2 = (h2[r] - h2[l - 1] * p2[r - l + 1]) % MOD2;
    if (res2 < 0) res2 += MOD2;

    return make_pair(res1, res2);
}

// ================== CORE 2: KMP 周期性秒杀算子 ==================
int get_min_period(const string& s, int n) {
    nxt[0] = 0;
    int j = 0;
    for (int i = 1; i < n; ++i) {
        while (j > 0 && s[i] != s[j]) j = nxt[j - 1];
        if (s[i] == s[j]) j++;
        nxt[i] = j;
    }

    int max_len = nxt[n - 1]; // 整个字符串的最长公共前后缀长度
    int l = n - max_len;      // 潜在的最小正周期长度

    if (n % l == 0) {
        return l; // 致命踩坑点：唯有当整除条件成立时，l 才是合法合规的循环节
    }
    return n; // 否则，说明无整周期循环，自身即为唯一最小周期
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    if (cin >> s) {
        int n = s.length();

        // 测试 1：KMP 最小周期秒杀
        int period = get_min_period(s, n);
        cout << "Min Period Length: " << period << " (Repeated " << n / period << " times)\n";

        // 测试 2：双 Hash 系统初始化
        init_hash(s, n);
        if (n >= 4) {
            // 抽取前两个字符组成的子串，与随后两个字符组成的子串，进行哈希对冲验证
            pair<long long, long long> sub1 = get_sub_hash(1, 2);
            pair<long long, long long> sub2 = get_sub_hash(3, 4);
            if (sub1 == sub2) {
                cout << "Substrings [1,2] and [3,4] are strictly equal.\n";
            } else {
                cout << "Substrings [1,2] and [3,4] are different.\n";
            }
        }
    }
    return 0;
}

NOIP 实战避坑指南

1. 差分取模时直接返回负数引发死WA

在执行 (h1[r] - h1[l - 1] * p1[r - l + 1]) % MOD1 时，由于减法操作在模运算下可能导致前半部分小于后半部分，算出的中间结果为负数。在 C++ 寻址与算术标准中，负数取模结果依旧是负数。如果不进行 if (res < 0) res += MOD 的强行修正，该负数哈希值在与别处的正数哈希值进行对冲判断时，将发生不可逆转的误判，导致整段代码大面积 WA 爆零。

2. KMP 周期判定中忽略“整除”约束导致逻辑伪证

很多选手在利用 $next$ 数组求字符串最小循环节时，无脑认为 $L = N - next[N-1]$ 就是答案。警告：若原串为 abaab，其 $N = 5$，最长公共前后缀为 ab（长度为 2），算出的 $L = 5 - 2 = 3$。然而 abaab 显然无法由 aba 连续重复拼出。 必须严格执行 if (n % l == 0) 的前置约束判定。若不整除，最小循环节长度只能是原串总长 $N$。忽略此步将直接在周期性计数题目中被特殊构造的测例精准狙击。

经典 NOIP/洛谷真题

1. 洛谷 P3370 【模板】字符串哈希

题意描述：给定 $N$ 个长度不超过 $M$ 的字符串，求其中互不相同的字符串一共有多少个。
问题本质：大范围字符串的去重判定。
核心解题思路：如果直接使用 std::set<string>，时间复杂度带有巨大的字符串拷贝和内部红黑树平移常数，极易超时。硬核写法是：使用本节的双 Hash 算法，对这 $N$ 个字符串分别计算出对应的 pair<long long, long long> 二元特征码。将所有的二元特征码塞入一个 std::vector 中，最后对该 vector 执行一次标准 sort 并配合 unique 算子去重。由于数字比对的时间复杂度为 $O(1)$，整体效率被牢牢压制在极其高能的 $O(N \log N + NM)$，可轻松抗住线上任何恶性碰撞测例。

2. 洛谷 P4391 [BJOI2006] Radio Transmission 无线传输

题意描述：给你一个长度为 $N$ 的字符串，它是由某个更短的字符串 $S$ 不断自我复制并截断产生的。求源字符串 $S$ 的最小可能长度。
问题本质：前缀函数周期性边界切分。
核心解题思路：此题是 KMP 周期性定理的超级变体。题目要求的是“潜在的”最小周期，这意味着末尾哪怕残缺了一部分也无所谓。由周期性定理的推导过程可知，无论结尾处是否能够整除，原串向右平移 $L = N - next[N-1]$ 位后，其重叠部分的公共错位结构依然能够完全对齐。这个 $L$ 恰恰代表了能够平铺衍生出当前母串的最小滑块长度。因此，不需要进行任何 n % l == 0 的判定，直接输出 $N - next[N-1]$ 即可在 $O(N)$ 复杂度内彻底秒杀该题。