Submission #8511

#	Time	Username	Problem	Language	Result	Execution time	Memory
8511		cki86201	Palindromes (APIO14_palindrome)	C++98	100 / 100	804 ms	34780 KiB

palindrome

#include<stdio.h>
#include<algorithm>

#define N_ 300030
#define LN 20

char ch[N_];
int N;
int SA[N_], RA[N_], tRA[N_], C[N_], tSA[N_];
int LCP[N_][LN], iSA[N_];
char S[N_<<1];
int P[N_<<1];
long long ans;

int main(){
	scanf("%s",ch);
	while(ch[++N]);
	int i, cnt = 128;
	for(i=0;i<N;i++)SA[i] = i, RA[i] = ch[i];
	for(int L=1;L<N;L<<=1){
		for(i=0;i<N;i++)++C[i+L < N ? RA[i+L] : 0];
		for(i=1;i<=cnt;i++)C[i] += C[i-1];
		for(i=N-1;i>=0;i--)tSA[--C[i+L < N ? RA[i+L] : 0]] = i;
		for(i=0;i<=cnt;i++)C[i] = 0;
		for(i=0;i<N;i++)++C[RA[i]];
		for(i=1;i<=cnt;i++)C[i] += C[i-1];
		for(i=N-1;i>=0;i--)SA[--C[RA[tSA[i]]]] = tSA[i];
		for(i=0;i<=cnt;i++)C[i] = 0;
		for(i=0,cnt=1;i<N;i++){
			if(i!=0 && (RA[SA[i]] != RA[SA[i-1]] || (SA[i]+L<N?RA[SA[i]+L]:0) != (SA[i]+L<N?RA[SA[i-1]+L]:0)))cnt++;
			tRA[i] = cnt;
		}
		for(i=0;i<N;i++)RA[SA[i]] = tRA[i];
	}
	for(i=0;i<N;i++)iSA[SA[i]] = i;
	int L;
	for(i=0,L=0;i<N;LCP[iSA[i++]][0] = L, L = (L?L-1:0)){
		if(iSA[i] == 0)continue;
		while(ch[i+L] == ch[SA[iSA[i]-1]+L])L++;
	}
	for(i=0;i<N;i++)
		for(int j=1;j<LN;j++){
			if(i < (1<<j))break;
			LCP[i][j] = std::min(LCP[i][j-1], LCP[i-(1<<(j-1))][j-1]);
		}
	for(i=0;i<N;i++)S[i<<1] = ch[i], S[i<<1|1] = '#';
	int M = N+N-1, c = -1, r;
	for(i=0;i<M;i++){
		if(i <= c && P[r+r-i] < c-i)P[i] = P[r+r-i];
		else{
			r = i;
			while(c+1 < M && c < i+i && S[c+1] == S[i+i-c-1]){
				if(c++ & 1){
					int rr = iSA[(i+i-c)>>1], ll = rr, len = c-i+1;
					for(int j=LN-1;j>=0;j--)if(rr+(1<<j) < N && LCP[rr+(1<<j)][j] >= len)rr += 1<<j;
					for(int j=LN-1;j>=0;j--)if(LCP[ll][j] >= len){
						ll -= 1<<j;
					}
					ans = std::max(ans, (long long)(rr - ll + 1) * len);
				}
			}
			P[i] = c-i;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27