yukicoder : No.464 PPAP

今更ではありますが。
https://yukicoder.me/problems/no/464

問題

N文字の文字列Sが与えられる。
Sを1文字以上の４つの文字列を連結したものとして表現するとき、(回文)+(回文)+(任意の文字列)+(回文)の形となるものは何通りか。

解法

まずDPでO(N^2)通りの部分文字列が回文かどうか判定しよう。
その結果を使いやはりO(N^2)でSの全てのprefixが2つの回文の連結で表現できるか、またそれが何通りかを判定しよう。
ここまで行くと、あとは(任意の文字列)の部分を総当たりし、その手前が回文の連結で、後ろが回文であるようなものを数え上げよう。

int L;
string S;
int par[5010][5010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	L=S.size();
	
	FOR(i,L) par[i][i+1]=1;
	FOR(i,L-1) if(S[i]==S[i+1]) par[i][i+2]=1;
	for(i=3;i<=L;i++) {
		for(x=0;x+i<=L;x++) if(par[x+1][x+i-1] && S[x]==S[x+i-1]) par[x][x+i]=1;
	}
	ll ret=0;
	for(i=2;i<=L;i++) {
		y=0;
		for(x=1;x<i;x++) if(par[0][x] && par[x][i]) y++;
		for(x=1;i+x<L;x++) if(par[L-x][L]) ret+=y;
	}
	cout<<ret<<endl;
}

まとめ

各処理がことごとくO(N^2)なのが面白い。