Submission #8099

#	Time	Username	Problem	Language	Result	Execution time	Memory
8099		cki86201	Palindromes (APIO14_palindrome)	C++98	0 / 100	0 ms	54704 KiB

palindrome

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

const int L_ = 300030;
const int LL = 20;
char ch[L_], ch2[L_+L_];
int ord[L_+L_], sa[L_];
int tmp[LL][L_], T, n;
int D[L_+L_];
int LCP[L_][LL];
long long ans;

bool comp(const int &a, const int &b){return ord[a] != ord[b] ? ord[a] < ord[b] : ord[a+T] < ord[b+T];}

int main(){
	scanf("%s",ch);
	int i, now = 0;
	for(i=0;ch[i];i++)sa[i] = i, ord[i] = ch[i];
	n = i;
	while(T<n){
		std::sort(sa,sa+n,comp);
		int cnt = 0;
		for(i=0;i<n;i++){
			if(i!=0 && (ord[sa[i]] != ord[sa[i-1]] || ord[sa[i]+T] != ord[sa[i-1]+T]))cnt++;
			tmp[now][sa[i]] = cnt;
		}
		for(i=0;i<n;i++)ord[i] = tmp[now][i];
		T = T?2*T:1;
		now++;
	}
	for(i=0;i<n;i++)sa[ord[i]] = i;
	for(i=1;i<n;i++){
		int x = sa[i], y = sa[i-1];
		for(int j=now-1;j>=0;j--)if(tmp[j][x] == tmp[j][y]){
			x += 1<<j, y += 1<<j, LCP[i][0] += 1<<j;
		}
		for(int j=1;j<LL;j++){
			if(i < (1<<j))break;
			LCP[i][j] = std::min(LCP[i][j-1], LCP[i-(1<<j)][j-1]);
		}
	}
	for(i=0;i<n;i++){
		ch2[i+i] = ch[i];
		ch2[i+i+1] = '-';
	}
	int m = 2*n-1, c = -1, r;
	for(i=0;i<m;i++){
		if(c >= i && D[r+r-i] < c-i)D[i] = D[r+r-i];
		else{
			r = i;
			while(c+1 < m && c < i+i && ch2[c+1] == ch2[i+i-c-1]){
				if(!(++c & 1)){
					int S = (i+i-c)/2, len = c-i+1;
					int right = ord[S], left = ord[S];
					for(int j=LL-1;j>=0;j--)if(right+(1<<j) < n && LCP[right+(1<<j)][j] >= len)right += 1<<j;
					for(int j=LL-1;j>=0;j--)if(left >= (1<<j) && LCP[left][j] >= len)left -= 1<<j;
					ans = std::max(ans, (long long)(right - left + 1) * len);
				}
			}
			D[i] = c - i;
		}
	}
	printf("%lld",ans);
	return 0;
}

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