那个,用哈希是不是会超时啊
查看原帖
那个,用哈希是不是会超时啊
836104
cxlian25楼主2022/12/25 16:12
 #include <bits/stdc++.h>
using namespace std;
const int N=1e7+1e6+3;
int n;
struct Hash{
    const int mod=1e9+7,u=131;
    int h[N],b[N];
    void build(char*s){
        int l=strlen(s+1);
        h[0]=0;b[0]=1;
        for(int i=1;i<=l;i++){
            h[i]=(1ll*h[i-1]*u+s[i]-'a'+1)%mod;
            b[i]=(1ll*b[i-1]*u)%mod;
        }
    }
    int gethash(int l,int r){
        return (h[r]-1ll*h[l-1]*b[r-l+1]%mod+mod)%mod;
    }
}ha1,ha2;
bool check(int l,int r){
    if(l<1||r>n)return false;
    return ha1.gethash(l,r)==ha2.gethash(n-r+1,n-l+1);
}
int main(){
    char a[N],t[N];
    scanf("%s",a+1);
    n=strlen(a+1);
    for(int i=1;i<=n;i++){
        t[i]=a[i];
    }
    reverse(t+1,t+1+n);
    ha1.build(a);
    ha2.build(t);
    int ans1=0,ans2=0;
    for(int i=1;i<=n;i++){
        while(check(i-ans1,i+ans1))ans1++;
    }
    for(int i=1;i<=n;i++){
        while(check(i-ans2,i+ans2+1))ans2++;
    }
    printf("%d",max(ans1*2-1,ans2*2));
    return 0;
}
2022/12/25 16:12
加载中...