前置芝士：字符串常用方法
推荐文章：花的哈希基础介绍
其中讲了无错哈希和多重哈希，但没讲如何 \(O(1)\) 求出子串哈希值。
这里把字符串 \(s\) 看成 \(p\) 进制数，使用自然溢出法。
技巧：子串哈希
我们可以用 \(O(n)\) 的时间预处理出所有前缀的 hash 值，然后可以 \(O(1)\) 求出子串哈希值。
具体地，令 \(f_{1…i}\) 表示 \(s_{1…i}\) 的哈希值，则有：
\(f_i=f_{i-1}\times p+s_i\)
就是向右挪一位再在最低位加一个数。
如果要求出 \([l,r]\) 的哈希值，可以这样做：
\(hash(l,r)=f_r-f_{l-1}\times p^{r-l+1}\)
就是把 \(s_{1…l-1}\) 挪到最高位再减掉。
例如：
\(\mathtt{abcdef}\)
欲求 \(hash(3,6)\) 即 \(\mathtt{cdef}\) 的哈希值（简称为 \(\overline{cdef}\)）。
我们预处理后知道 \(f_2\) 和 \(f_6\)。
也就是知道了 \(\overline{abcdef}\) 和 \(\overline{ab}\)。
但是这两个不能直接相减，要把 \(\overline{ab}\) 挪到数位对齐。
于是我们把 \(\overline{ab}\) 变成 \(\overline{ab0000}\)，也就是把 \(f_2\) 乘上了
\(p^4\)。
相减:
\[\;\;\quad\;\overline{abcdef} \]\[-\quad\;\overline{ab0000} \]\[=\quad\overline{00cdef} \]省略 \(0\) 就变成了 \(\overline{cdef}\)。
总结
预处理：
\(f_i=f_{i-1}\times p+s_i\)（这里的 \(s_i\) 最好定义为减 'a' 加 1）
求 \([l,r]\) 的哈希值：
\(hash(l,r)=f_r-f_{l-1}\times p^{r-l+1}\)（最好提前处理出 \(p\) 的次幂）
例 1：138. 兔子与兔子
子串哈希裸题。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5,p=131;
typedef unsigned long long ull;
string s;
ull f[maxn],pwr[maxn];
void init()
{
pwr[0]=1;
for(int i=1;i<s.size();i++)pwr[i]=pwr[i-1]*p;
for(int i=1;i<s.size();i++)f[i]=f[i-1]*p+(s[i]-'a'+1);
}
ull ask(int l,int r){return f[r]-f[l-1]*pwr[r-l+1];}
int main()
{
cin>>s;s.insert(0,"0");
init();
int T;
cin>>T;
for(int i=1;i<=T;i++)
{
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(ask(l1,r1)==ask(l2,r2))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
例 2：139. 回文子串的最大长度
将字符串正着和倒着 hash 一遍，如果一个串正着和倒着的 hash 值相等则这个串是回文串。枚举每个节点以及每个分割点为回文中心，二分即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5,p=131;
typedef unsigned long long ull;
string s;
ull f[maxn],g[maxn],pwr[maxn];
int ans;
void init()
{
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
memset(pwr,0,sizeof(pwr));
ans=0;
pwr[0]=1;
for(int i=1;i<s.size();i++)pwr[i]=pwr[i-1]*p;
for(int i=1;i<s.size();i++)f[i]=f[i-1]*p+(s[i]-'a'+1);
for(int i=s.size()-1;i>=1;i--)g[i]=g[i+1]*p+(s[i]-'a'+1);
}
ull ask1(int l,int r){return f[r]-f[l-1]*pwr[r-l+1];}
ull ask2(int l,int r){return g[l]-g[r+1]*pwr[r-l+1];}
bool check1(int cntr,int x)
{
int l=cntr-x,r=cntr+x;
if(ask1(l,r)==ask2(l,r))
return 1;
return 0;
}
bool check2(int cntr,int x)
{
int l=cntr-x+1,r=cntr+x;
if(ask1(l,r)==ask2(l,r))
return 1;
return 0;
}
int main()
{
for(int c=1;;c++)
{
cin>>s;
if(s=="END")
break;
s.insert(0,"0");
init();
for(int i=1;i<s.size();i++)
{
int l=0,r=min(i-1,(int)s.size()-i-1),res=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(check1(i,mid))
{
res=mid;
l=mid+1;
}
else
r=mid-1;
}
ans=max(ans,1+2*res);
l=0,r=min(i,(int)s.size()-i-1),res=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(check2(i,mid))
{
res=mid;
l=mid+1;
}
else
r=mid-1;
}
ans=max(ans,2*res);
}
cout<<"Case "<<c<<": "<<ans<<endl;
}
return 0;
}