oj.uz

Submission #8510

# Submission time Handle Problem Language Result Execution time Memory
8510 2014-09-15T05:38:58 Z cki86201 Palindromes (APIO14_palindrome) C++
0 / 100
 0 ms 34780 KB 
#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++;
	}LCP[0][0] = 0;
	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(ll >= (1<<j) && 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
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 34780 KB Output is correct - answer is '7'
2 Correct 0 ms 34780 KB Output is correct - answer is '4'
3 Correct 0 ms 34780 KB Output is correct - answer is '9'
4 Correct 0 ms 34780 KB Output is correct - answer is '1'
5 Correct 0 ms 34780 KB Output is correct - answer is '1'
6 Correct 0 ms 34780 KB Output is correct - answer is '2'
7 Correct 0 ms 34780 KB Output is correct - answer is '3'
8 Correct 0 ms 34780 KB Output is correct - answer is '3'
9 Correct 0 ms 34780 KB Output is correct - answer is '15'
10 Correct 0 ms 34780 KB Output is correct - answer is '24'
11 Correct 0 ms 34780 KB Output is correct - answer is '10'
12 Correct 0 ms 34780 KB Output is correct - answer is '24'
13 Correct 0 ms 34780 KB Output is correct - answer is '25'
14 Correct 0 ms 34780 KB Output is correct - answer is '28'
15 Correct 0 ms 34780 KB Output is correct - answer is '2'
16 Correct 0 ms 34780 KB Output is correct - answer is '1'
17 Correct 0 ms 34780 KB Output is correct - answer is '15'
18 Incorrect 0 ms 34780 KB Output isn't correct - expected '18', found '15'
19 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -