5TLE求助
查看原帖
5TLE求助
1258467
hao12345ia楼主2024/8/28 15:20
#include<bits/stdc++.h>
using namespace std;    int rt=1,mid=1;
    int ans=1;
int n, m;int p[59000000];
char s[59000000], str[59000000];
int manacher(){

    for(int i=1;i<=m; i++) {
    	if(i<rt){
    		p[i]=min(p[mid*2-1],rt-i);
		}
		else{
			p[i]=1;
		}
        while(str[i+p[i]]==str[i-p[i]]){
			p[i]++;
		}
        if(i+p[i]>rt) {
            rt=i+p[i];
            mid=i;
        }
        ans=max(ans,p[i]-1);
    }
    
	return ans;
}
int main() {
	str[0]='!';
	str[1]='#';
	scanf("%s",s);
    n=strlen(s);
    for(int i=0;i<n;i++) {
        str[i*2+2]=s[i];
        str[i*2+3]='#';
    }
    m=n*2+2;
    str[m+1]='@';
    printf("%d",manacher());
}
2024/8/28 15:20
加载中...