CSAcademy Round #27 : E. Palindrome Centers

一応レート増だけどなかなかに苦戦。
https://csacademy.com/contest/round-27/task/palindrome-centers/

問題

ある文字列Sがあったとする。　
長さ|S|の配列Aが与えられる。
A[i]はS[i]を末尾とするSの部分文字列のうち最長の回文長を示す。

Sの各文字を中心とした回文の最大長を求めよ。

解法

Sを復元後、Manacherのアルゴリズムで各文字を中心とする回文の最大長を求める。
Sの復元には、基本的にすべての文字は異なっているとしつつ、Union-FindでS[i]とS[i-(A[i]-1)]を同一とみなしていけばよい。

int N;
int S[101010];
int ret[101010];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

pair<vector<int>,pair<int,int> > manacher(vector<int> S) {
	int L=S.size(),i,j,k;
	vector<int> rad(2*L-1,0);
	for(i=j=0;i<2*L-1;i+=k,j=max(j-k,0)) {
		while(i-j>=0 && i+j+1<=2*L-1 && S[(i-j)/2]==S[(i+j+1)/2]) j++;
		rad[i]=j;
		for(k=1;i-k>=0 && rad[i]-k>=0 && rad[i-k]!=rad[i]-k; k++) rad[i+k]=min(rad[i-k],rad[i]-k);
	}
	i=max_element(rad.begin(),rad.end())-rad.begin();
	return make_pair(rad,make_pair((i-(rad[i]-1))/2,(i+(rad[i]-1))/2));
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i];
		uf(i,i-(S[i]-1));
	}
	vector<int> SS;
	FOR(i,N) SS.push_back(uf[i]);
	vector<int> rad=manacher(SS).first;
	
	FOR(i,N) _P("%d%c",rad[i*2],(i==N-1)?'\n':' ');
}

まとめ

Manacherは文字列全体における最大長の回文を求めるアルゴリズムと勘違いしていて回答が遅れた。