求助,acwing过了,洛谷RE了0分
查看原帖
求助,acwing过了,洛谷RE了0分
530797
code_hyx楼主2023/1/7 17:40

是数组开小了吗?应该也不小吧

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int P=131;
ull h1[12000005],h2[12000005],p[12000005];
char str[12000005];
ull gethash(ull h[],int l,int r) 
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main() 
{
	int cnt=1;
	cin>>(str+1);
    int n=strlen(str+1);
    for(int i=n*2;i>0;i-=2) 
	{
        str[i]=str[i/2];
        str[i-1]='a'+26;
    }
    //cout<<str<<"\n";
    n*=2;
    p[0]=1;
    for(int i=1,j=n;i<=n;i++,j--) 
	{
        h1[i]=h1[i-1]*P+str[i];
        h2[i]=h2[i-1]*P+str[j];
        p[i]=p[i-1]*P;
    }
    int ans=0;
    for(int i=1;i<=n;i++) 
	{
        int l=0,r=min(i-1,n-i);
        while(l<r) 
		{
			//cout<<l<<" "<<r<<"\n";
            int mid=(l+r+1)/2;
            if(gethash(h1,i-mid,i-1)!=gethash(h2,n-i-mid+1,n-i)) 
			{
                r=mid-1;
            } 
			else 
			{
                l=mid;
            }
        }
        if(str[i-l]<='z') 
		{
            ans=max(ans,l+1);
        } 
		else 
		{
            ans=max(ans,l);
        }
    }
    cout<<ans;
    return 0;
}

2023/1/7 17:40
加载中...