TLE #2 #5 #7求大佬调
查看原帖
TLE #2 #5 #7求大佬调
1173481
xjm114514楼主2024/7/24 07:17

rt

#include<bits/stdc++.h>
using namespace std;
char s[114514*5];
int n,ans=0;
int cnt=1,fail[114514*5],trans[114514],dep[114514*5],len[114514*5],ch[114514*5][26];
signed main(){
	cin >> n;
	cin >> s+1;
	s[0]='#';
	
	int las=0;
	fail[0]=1;
	len[1]=-1;
	for(int i=1;i<=n;i++){
		//if(i!=1) s[i]=(s[i]-97+ans)%26+97;
		while(s[i-len[las]-1]!=s[i]) las = fail[las];
		if(!ch[las][s[i]-'a']){
			len[++cnt]=len[las]+2;
			int j = fail[las];
			while(s[i-len[j]-1]!=s[i]) j = fail[j];
			fail[cnt]=ch[j][s[i]-'a'];
			ch[las][s[i]-'a']=cnt;
			if(len[cnt]<=2) trans[cnt] = fail[cnt];
			else {
				int tmp = trans[las];
				while(s[i-len[tmp]-1]!=s[i] or (len[tmp]+2)*2>len[cnt]) tmp = fail[tmp];
				trans[cnt] = ch[tmp][s[i]-'a'];
			}
			dep[cnt]=dep[fail[cnt]]+1;
		}
		las = ch[las][s[i]-'a'];
	}
	for(int i=1;i<=n;i++){
		if(len[trans[i]]*2==len[i] and len[trans[i]]%2==0) ans = max(ans,len[i]);
	}
	cout << ans;
	return 0;
}

2024/7/24 07:17
加载中...