字符串哈希实战：快速查找与回文检测

从生活中的例子引入

上一讲我们学会了给字符串做“数字指纹”（哈希值）。有了这个工具，我们可以解决很多实际问题。比如：

在一大段文字中快速查找某个单词（子串匹配）——就像在一本书里找一句名言，你不需要逐字对照，而是先计算名言的指纹，再用指纹比照书中每段文字的指纹。想象一下，老师让你在一篇5000字的作文里找出所有出现“努力”的地方。如果暴力做法是一字一字地滑动比较，那得花好几分钟；而哈希法就像把所有“努力”出现的位置提前贴好标签，瞬间就能找到。
判断一个字符串是否回文（正反读一样）——比如“上海自来水来自海上”。传统方法要双向比较，哈希法只需比较正向哈希和反向哈希是否相等。就像你给一句话拍一张正面照片和一张背面照片，如果两张照片一模一样，那这句话就是回文。

本节课我们就来学习这两个非常实用的应用。

子串匹配：用哈希代替暴力，又快又省力

假设我们有一个文本串T（长度n）和一个模式串P（长度m），要在T中找出所有出现P的位置。比如：T = “ABABAB”，P = “ABA”，我们要找到P在T中所有的起始位置。

传统暴力方法

暴力做法是：枚举每个起始位置（0到n-m），然后逐字符比较，看看是否完全相等。比如从位置0开始比较“A B A”和“A B A”匹配，从位置1比较“B A B”和“A B A”不匹配，从位置2比较......时间复杂度是O(n*m)。如果n=10000，m=100，就要比较1000000次，太慢了。

哈希方法如何提速

哈希方法的核心思想：先用一个O(m)的时间计算出模式串P的哈希值，然后用滚动哈希O(1)计算出文本串中每个长度为m的子串的哈希值，最后比较哈希值是否相等。这样整体复杂度降到O(n+m)。下面我们详细拆解。

1. 计算模式串的哈希值

和上一节一样，我们给字符串建立前缀哈希。对于模式串P，我们可以直接用双哈希计算它的哈希值。例如P="ABA"，假设base=131，模数mod1=1e9+7，mod2=1e9+9，则哈希值是一个二元组。

2. 用滚动哈希快速得到文本串的每个子串哈希

我们之前已经学会了如何预处理文本串的前缀哈希数组pre[]，然后通过公式： hash(l, r) = (pre[r+1] - pre[l] * base^(r-l+1)) % mod 就能在O(1)时间内得到任意子串的哈希值。注意：由于减法可能产生负数，需要加mod再取模。

3. 比较匹配

对于文本串的每个起始位置i（0 ≤ i ≤ n-m），我们计算子串T[i...i+m-1]的哈希值，与模式串哈希值比较。如果相等，就说明可能匹配。为了消除哈希冲突的隐患，我们通常使用双哈希（两个不同的模数），或者当哈希匹配时再额外比较一次原始字符。

举个例子

文本T = "ABABAB"，模式P = "ABA"，我们来模拟一下：

计算P的哈希值：假设得到(100,200)（实际数字不同）。
计算T的前缀哈希。
遍历i=0: 子串T[0..2]="ABA"，哈希值(100,200) → 匹配！记录位置0。
i=1: 子串T[1..3]="BAB"，哈希值(150,300) → 不匹配。
i=2: 子串T[2..4]="ABA"，哈希值(100,200) → 匹配！记录位置2。
i=3: 子串T[3..5]="BAB"，不匹配。

最终找到位置0和2，结果正确。

ASCII示意图

T:  A B A B A B
    0 1 2 3 4 5
模式 P = "A B A"
子串[0..2]=ABA  → 匹配
子串[1..3]=BAB  → 不匹配
子串[2..4]=ABA  → 匹配
子串[3..5]=BAB  → 不匹配

回文判断：正反哈希的巧妙配合

回文字符串是指正着读和反着读完全一样，比如“ABA”、“上海自来水来自海上”。用哈希判断一个子串是不是回文，不需要把子串翻转再比较，而是利用原串的正向哈希和逆序串的正向哈希。

核心思想

构造原串s的正向哈希（前缀哈希）。
构造逆序串rev_s（即s的反转）的正向哈希。
对于原串的子串s[l..r]（区间左闭右闭），它在逆序串中对应的区间是什么？

关键映射：原串中位置l对应逆序串中的位置n-1-l，位置r对应逆序串中的位置n-1-r。因此，子串s[l..r]的逆序串对应的是rev_s中从n-1-r到n-1-l这段子串（注意顺序是反的，但rev_s本身已经是反转后的，所以我们直接取rev_s的[n-1-r, n-1-l]区间，它的顺序就是原串子串的逆序）。

所以，s[l..r]是回文，当且仅当： hash_s(l, r) == hash_rev(n-1-r, n-1-l)

其中hash_s是原串的正向哈希，hash_rev是逆序串的正向哈希。

为什么要这样映射？

假设s = "ABBA"，n=4。逆序串rev_s = "ABBA"（和原串相同，但这不是重点）。我们来看子串[1,2] = "BB"。

原串子串[1,2]的哈希：计算"BB"的哈希。
逆序串对应区间：n-1-r = 4-1-2 = 1，n-1-l = 4-1-1 = 2，所以区间是rev_s[1..2] = "BB"（因为rev_s[1]='B', rev_s[2]='B'），哈希相等 → 是回文。

再看子串[0,1] = "AB"：

原串哈希"AB"。
逆序串对应区间：n-1-r = 4-1-1 = 2，n-1-l = 4-1-0 = 3，区间rev_s[2..3] = "BA"（rev_s[2]='B', rev_s[3]='A'），哈希不相等 → 不是回文。

一个更直观的例子

考虑s = "racecar"，这是一个回文字符串。逆序串rev_s = "racecar"（一样）。原串子串[0,6]（整个串）的哈希等于逆序串子串[0,6]的哈希 → 是回文。原串子串[1,5] = "aceca"也是回文，对应的逆序串区间[1,5]也是"aceca" → 哈希相等。

生活中理解回文检测

你和同学在玩猜字游戏，对方说“上海自来水来自海上”，你如何快速判断它是不是回文？如果你会哈希法，你可以：

把这句话的正序写下来，计算哈希值。
把这句话倒序写下来，计算哈希值。
比较两个哈希值是否相等。如果相等，就是回文。

实际上，对于任意一个子串（比如“自来水来自”），你也能用同样的方法判断它是否为回文，只需要把原串子串的哈希和逆序串对应子串的哈希比较即可。

long long h1 = (pre1[r+1] - pre1[l]*pow1[r-l+1] % mod1 + mod1) % mod1;

+ mod1是关键，千万不要忘记。

3. 索引越界

前缀哈希数组pre的大小是n+1，pre[0]=0，pre[1]对应第一个字符。
在getHash(l, r)中，l和r是左闭右闭的原始下标，调用时注意：pre[r+1]不能越界。确保r+1 ≤ n。
逆序串的索引映射需要小心：revL = n-1-r, revR = n-1-l，要保证revL ≤ revR，且都在[0, n-1]范围内。当子串长度为1时，revL==revR完全正确。

4. base和模数的选择

base常用131、137、91138233等质数。
模数常用1e9+7、1e9+9，这两个都是大质数，且乘积在long long范围内。
不要用2的幂次（如1<<31），因为容易碰撞。

5. 字符编码

在C++中，直接用char的ASCII码（0-127）没问题，但如果是中文字符（多字节），需要将每个字符转换为整数值（比如用unsigned char），或使用宽字符。对于简单题目，英文字符串足够。

完整代码示例（C++和Python）

下面的代码实现了子串匹配和回文判断，使用了双哈希。我们已经在前面给出了完整的C++和Python代码，这里再强调几个要点：

DoubleHash类的构造函数中，我们计算了pow数组和pre数组。
getHash(l, r)返回pair<long long, long long>，注意区间是左闭右闭。
子串匹配时，只需遍历i从0到n-m，比较哈希。
回文判断时，构造逆序串，注意映射公式。

代码可以直接复制到IDE中运行。为了加深理解，也可以尝试修改text和pattern，测试不同情况。

字符串哈希的应用：子串匹配与回文判断