Submission #7616

#	Time	Username	Problem	Language	Result	Execution time	Memory
7616		myungwoo	Palindromes (APIO14_palindrome)	C++98	0 / 100	0 ms	8856 KiB

palindrome

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 600005

int N;
int R[MAXN],SA[MAXN],lcp[MAXN];
char A[MAXN];

void Manachers()
{
	int r = 0, p = 0;
	for (int i=1;i<=N;i++){
		if (i <= r) R[i] = min(R[2*p-i],r-i);
		else R[i] = 0;
		while (i > R[i] && A[i-R[i]-1] == A[i+R[i]+1]) R[i]++;
		if (r < i+R[i]) r = i+R[i], p = i;
	}
}

void SuffixArray()
{
	int i,j,k;
	int m = 27;
	vector <int> cnt(max(N,m)+1,0),x(N+1,0),y(N+1,0);
	for (i=1;i<=N;i++) cnt[x[i] = (A[i]=='#')?27:A[i]-'a'+1]++;
	for (i=1;i<=m;i++) cnt[i] += cnt[i-1];
	for (i=N;i;i--) SA[cnt[x[i]]--] = i;
	for (int len=1,p=1;p<N;len<<=1,m=p){
		for (p=0,i=N-len;++i<=N;) y[++p] = i;
		for (i=1;i<=N;i++) if (SA[i] > len) y[++p] = SA[i]-len;
		for (i=0;i<=m;i++) cnt[i] = 0;
		for (i=1;i<=N;i++) cnt[x[y[i]]]++;
		for (i=1;i<=m;i++) cnt[i] += cnt[i-1];
		for (i=N;i;i--) SA[cnt[x[y[i]]]--] = y[i];
		swap(x,y); p = 1; x[SA[1]] = 1;
		for (i=1;i<N;i++)
			x[SA[i+1]] = SA[i]+len <= N && SA[i+1]+len <= N && y[SA[i]] == y[SA[i+1]] && y[SA[i]+len] == y[SA[i+1]+len] ? p : ++p;
	}
}

void LCP()
{
	int i,j,k=0;
	vector <int> rank(N+1,0);
	for (i=1;i<=N;i++) rank[SA[i]] = i;
	for (i=1;i<=N;lcp[rank[i++]]=k)
		for (k?k--:0,j=SA[rank[i]-1];A[i+k]==A[j+k];k++);
}

int main()
{
	int i;
	scanf("%s",A+1); N = strlen(A+1);
	for (i=N;i;i--) A[i+i-1] = A[i]; N = N+N-1;
	for (i=2;i<N;i+=2) A[i] = '#';
	Manachers(); SuffixArray(); LCP();
	for (i=1;i<=N;i++){
		puts(A+SA[i]);
	}
}

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