字符串哈希与滚动窗口匹配

📖 算法原理：多项式哈希与 $O(1)$ 窗口滚动更新

字符串哈希（String Hash）把字符串 $S$ 视为一个庞大的 $P$ 进制正整数，再对一个大整数 $M$ 取模，映射到一维紧凑哈希槽中。它能将两串字符的高昂 $O(L)$ 判定开销化为瞬时的 $O(1)$ 整型比较。

📐 字符串哈希构造公式与前缀和性质

一个长度为 $W$ 的字符串 $S = S[0..W-1]$ 的多项式滚动哈希公式（模数选择 $M$ 质数，一般 C++ 中直接使用 unsigned long long 自然溢出，即 $M = 2^{64}$）：

$H(S) = (S[0] \times P^{W-1} + S[1] \times P^{W-2} + ... + S[W-1] \times P^0) \bmod M$

💡 Rabin-Karp 滚动窗口哈希的核心魔力：在长文本中匹配长度为 $W$ 的子串时，窗口从 $i-1$ 向右滑动到 $i$（移出左字符 $S[left]$，移入右字符 $S[right]$）。我们不需要重新循环计算长度为 $W$ 的子串，而可以直接从旧哈希值 $H_{old}$ 以 $O(1)$ 常数时间直接递推导出新值 $H_{new}$：

$H_{new} = \Big( (H_{old} - S[left] \times P^{W-1}) \times P + S[right] \Big) \bmod M$

这就是滚动哈希（Rolling Hash）的核心！它支持 Rabin-Karp 字符串搜索算法实现 $O(N + M)$ 线性查找！

目标匹配子串 (Target)：

演示速度：

输入需要匹配的子串并点击"开始滚动扫描"，观摩滑动扫描窗口内的多项式计算。

🔎 Rabin-Karp 滚动滑块扫描器 (Rabin-Karp Rolling Slider Grid)

Target 目标:

                            H(Target) = -
                        

暂无运行数据。点击“单步滑行”或“开始滚动”运行

typedef unsigned long long ull;
const ull P = 131; // 进制数(选择质数)
const ull M = 997; // 演示取模模数(防止数值溢出显示)

ull getHash(string s) {
    ull h = 0;
    for (char c : s) h = (h * P + c) % M;
    return h;
}

// O(1) 滚动哈希更新公式
ull rollHash(ull oldHash, char leftChar, char rightChar, ull pW) {
    // 1. 移去左侧字符：(oldHash - leftChar * P^(W-1))
    ull temp = (oldHash + M - (leftChar * pW) % M) % M;
    // 2. 左移并移入右侧字符：(temp * P + rightChar) % M
    return (temp * P + rightChar) % M;
}

📋 滚动哈希匹配历史步骤