晓宜
2022-05-19 08:36
采纳率: 33.3%
浏览 38

小蓝的01字符串,搞不懂第13行的判断条件中g为什么要+1

问题遇到的现象和发生背景

题目链接: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)

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

1条回答 默认 最新

相关推荐 更多相似问题