1 条题解

  • 0
    @ 2026-10-27 11:54:30

    马拉车板子。记得开两倍数组。

    #include<iostream>
    #include<algorithm>
    #include<vector>
    #define int long long
    using namespace std;
    const int N=1e6+7;
    string str;
    char s[N]={0,'#'};
    int d[N];
    int cnt;
    signed main(){
    	while(cin>>str && str!="END"){
    		int n=str.size(),ans=0;
    		str="#"+str;
    		for(int i=1;i<=n;i++) s[i<<1]=str[i],s[i<<1|1]='#';
    		n=n<<1|1;
    		for(int i=1;i<=n;i++) d[i]=0;
    		int mid=0,dis=0;
    		for(int i=1;i<=n;i++){
    			if(i<=mid+dis) d[i]=min(d[(mid<<1)-i],mid+dis-i);
    			if(i+d[i]>=mid+dis){
    				while(i+d[i]+1<=n && i-d[i]-1>=1 && s[i+d[i]+1]==s[i-d[i]-1])
    					d[i]++;
    				mid=i,dis=d[i];
    				ans=max(ans,dis);
    			}
    		}
    		cout<<"Case "<<++cnt<<": "<<ans<<'\n';
    	}
    	return 0;
    }
    
    

    信息

    ID
    608
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    9
    已通过
    3
    上传者