Problem 1203 : Napoleon's Grumble

問題概要

与えられた文字列に含まれる長さ3以上の回文を全て出力せよ。
ただし、他の回文の中央に完全に含まれるような回文は出力しない。
回文はどのような順番で出力してもよい。

また、元の文字列のアルファベット以外の文字は無視し、回文は英大文字で、スペース区切りで出力する。

解法

回文の全列挙はrolling hashを使ってO(n^2)でできる。
（過去に何度か解説書いたので参照）

回文が他の回文の中央に入っているかはナイーブに回文を全部調べても0msで通ったが、もう少し効率的にもできる。
（文字数の偶奇で分けて、一文字、二文字、三文字…の部分文字列を全てsetに入れる）

ソースコード

int main()
{
	string t; int n;
	while(getline(cin,t)){
		string s;
		fr(i,t)if(isalpha(*i))s.pb(toupper(*i));
		n=s.size();
		set<string> S;
		rep(i,n-2){
			ll h=0,H=0,b=1;
			int j=i;
			rep(k,2){
				h*=29; h+=s[j]-'A';
				H+=b*(s[j]-'A'); b*=29; j++;
			}
			for(;j<n;j++){
				h*=29; h+=s[j]-'A';
				H+=b*(s[j]-'A'); b*=29;
				if(h==H)S.insert(s.substr(i,j-i+1));
			}
		}
		vs v; fr(i,S)v.pb(*i);
		int m=v.size(); bool f=1;
		vector<int> len; rep(i,m)len.pb(v[i].size());
		rep(i,m){
			rep(j,m)if(i!=j){
				if(len[i]<len[j]&&v[i]==v[j].substr((len[j]-len[i])/2,len[i]))goto FAIL;
			}
			if(!f)cout<<" "; else f=0;
			cout<<v[i]; FAIL:;
		}
		cout<<endl;
	}
	return 0;
}