本章节将介绍哈希如何实现 KMP 与 manacher。
KMP
我们对于文本串 \(s\) 和模式串 \(t\)，先用一个数组 \(has_i\) 表示 \(s\) 中 前 \(i\) 位的哈希值，用 \(hat\) 表示 \(t\) 的哈希值。
然后遍历 \(s\)，计算以第 \(i\) 位为起点的长度为 \(|t|\) 的区间的哈希值，与 \(hat\) 比较，累加答案即可。
跑得飞快。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int maxn=1e6+10;
char s[maxn],t[maxn];
int n,m,ans;
int hat,has[maxn],p[maxn]={1};
int work(int l,int r)
{
return has[r]-has[l-1]*p[r-l+1];
}
signed main()
{
cin>>(s+1)>>(t+1);
n=strlen(s+1),m=strlen(t+1);
for(int i=1;i<=n;i++)
{
has[i]=has[i-1]*131+(s[i]-'0');
p[i]=p[i-1]*131;
}
for(int i=1;i<=m;i++)hat=hat*131+(t[i]-'0');
for(int l=1;l<=n-m+1;l++)
{
int r=l+m-1;
if(work(l,r)==hat)ans++;
}
cout<<ans;
return 0;
}
manacher
这个稍微复杂一点，不过也不难。
设原字符串为 \(s\)，先预处理从后往前和从前往后两个哈希数组，设为 \(fr\) 和 \(en\)。那么对于一个子串 \(s_{l,r}\)，设 \(get1\)，\(get2\) 分别为两个哈希数组对于该区间的哈希值，那么它是回文串的充要条件为 \(get1=get2\)，从而可以做到 \(\mathcal{O}(1)\) 判断回文串。
朴素做法是 \(\mathcal{O}(n^3)\) 的，用上述做法可以优化到 \(\mathcal{O}(n^2)\)，依然过不去，怎么办呢？
考虑设 \(dp_r\) 表示以 \(r\) 结尾的最长回文串长度。容易发现如果一个回文串以 \(r\) 结尾，如果把长度为 \(1\) 的串特判掉以后，它一定是由一个以 \(r-1\) 结尾的回文串拼接两个字符组成的。
所以就找到以 \(r-1\) 结尾的回文串之前的那个字符，容易推出它的位置是 \(r-dp_{r-1}\)，然后我们定义 \(l\) 为从刚刚提到的位置向右移动时当前的位置，那么我们用哈希 \(\mathcal{O}(1)\) 判断当前串 \([l,r]\) 是否为回文串，然后如果是跳出循环，否则 \(l++\) 即可。
最后遍历 \(dp\) 数组，找到最大值输出即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int maxn=1.1e7+10;
char s[maxn];
int n,fr[maxn],en[maxn],p[maxn];
int dp[maxn];
bool check(int l,int r)
{
int get1=fr[r]-fr[l-1]*p[r-l+1];
int get2=en[l]-en[r+1]*p[r-l+1];
return get1==get2;
}
signed main()
{
cin>>(s+1);
n=strlen(s+1);p[0]=1;
for(int i=1;i<=n;i++){fr[i]=fr[i-1]*171+(s[i]-'0');p[i]=p[i-1]*171;}
for(int i=n;i>=1;i--){en[i]=en[i+1]*171+(s[i]-'0');}
dp[1]=1;dp[2]=(s[1]==s[2]?2:1);
for(int r=3;r<=n;r++)
{
int l=r-dp[r-1];
if(l!=1)l--;
while(l<r)
{
if(check(l,r))break;
l++;
}
dp[r]=r-l+1;
}
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,dp[i]);
cout<<ans;
return 0;
}