问题遇到的现象和发生背景
题目链接:https://www.lanqiao.cn/problems/1627/learning/
问题相关代码,请勿粘贴截图
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 5e5+10;
char s[N],t[N];
int n,PP =131;
long long ans;
ull P[N],f[N],g[N]; //P:计算p的i次方,f:s的前缀哈希值,g:t的前缀哈希值
void bin_search(int x){ //用二分法寻找以s[x]为中心的回文串
int L=0,R=min(x,n-x);
while(L<R){
int mid = (L+R+1)>>1;
if((ull)(f[x]-f[x-mid]*P[mid])==(ull)(g[x+1]-g[x+1+mid]*P[mid]))
L = mid;
else R = mid-1;
}
ans += L; //最长回文串的长度是L,它内部有L个回文串
}
int main(){
scanf("%d",&n); scanf("%s",s+1);
P[0] = 1;
for(int i=1;i<=n;i++) s[i]=='1'? t[i]='0':t[i]='1'; //t是反串
for(int i=1;i<=n;i++) P[i] = P[i-1]*PP; //P[i]=PP的i次方
for(int i=1;i<=n;i++) f[i] = f[i-1]*PP + s[i]; //求s所有前缀的哈希值
for(int i=n;i>=1;i--) g[i] = g[i+1]*PP + t[i]; //求t所有前缀的哈希值
for(int i=1;i<n;i++) bin_search(i);
printf("%lld\n",ans);
return 0;
}
我想要达到的结果
求解释一下哈希值判断的逻辑
if((ull)(f[x]-f[x-mid]*P[mid])==(ull)(g[x+1]-g[x+1+mid]*P[mid]))
我倒是知道哈希值中两个字符串的组合S1+S2 的哈希值为 H(S1) × Plen(S2) + H(S2)