Codeforces Global Round 7 : D2. Prefix-Suffix Palindrome (Hard version)

まぁまぁの順位で割とレートを稼いだ回。
http://codeforces.com/contest/1326/problem/D2

問題

文字列Sが与えられる。Sのprefix aとsuffix bを選んでT=a+bを作るとき、以下の条件を満たす最長の文字列を求めよ。

• |T|≦|S|
• Tは回文

解法

色々解法がありそう。
元々Sのprefixとsuffixで(反転して)一致する部分はa,bに含んでおく。
これらを除いた文字列S'を考える。

S'の先頭と末尾は異なるので、両方Tに含むことはあり得ない、そこで先頭か末尾かどちらかを含む最長の回文を求めよう。
これにはManacherを用いることでO(|S'|)で対応できる。

こういろいろ書いたけど、Sを反転したものをSにくっ付けてZ-algorithm使う方がラクかもね。

int T;
int N;
string S;

pair<vector<int>,pair<int,int> > manacher(string 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>>T;
	while(T--) {
		cin>>S;
		N=S.size();
		
		FOR(x,N) {
			if(S[x]!=S[N-1-x]) break;
		}
		
		if(x==N) {
			cout<<S<<endl;
			continue;
		}
		string A=S.substr(0,x);
		string B=S.substr(N-x);
		string C=S.substr(x,N-2*x);
		vector<int> V=manacher(C).first;
		int best=0,id=-1;
		FOR(i,V.size()) {
			if((V[i]==i+1 || V[i]+i==V.size()) && V[i]>best) best=V[i],id=i;
		}
		
		if(best==0) {
			C="";
		}
		else if(best%2==0) {
			FOR(i,best) A+=C[(id-(best-1))/2+i];
		}
		else {
			FOR(i,best) A+=C[(id-(best-1))/2+i];
		}
		cout<<A+B<<endl;
		
		
	}
}

まとめ

思った以上に解いた人数多いなこれ。