Codeforces #635 Div1 C. Kaavi and Magic Spell

もう12月か…。
https://codeforces.com/contest/1336/problem/C

問題

文字列S,Tが与えられる。
空文字Aがあるので、Sの先頭から順に、1文字ずつAの先頭または末尾に追加していくとする。
なお、Sの全文字を処理しなくても、途中で止めてもよい。
最後AのprefixがTと一致するのは何通りか。

解法

dp(L,R) := Sのうち(R-L)文字まで処理を行ったとき、Aのうち区間[L...R)が埋まっていてかつこれらがprefixがTと矛盾しない組み合わせ
とする。
最初の1文字目は総当たりし、dp(0,1)、dp(1,2)、dp(2,3)…とそれぞれに当てはまるか見ていって初期値を増やしていこう。
以後、(R-L)の小さい順にこのテーブルを埋めて行ってdp(0,|T|)～dp(0,|S|)の和を答える。

string S,T;
int N,M;
const ll mo=998244353;

ll dp[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	N=S.size();
	M=T.size();
	
	FOR(i,N) {
		if(i>=M || T[i]==S[0]) dp[i][i+1]=2;
	}
	for(int pos=1;pos<N;pos++) {
		for(x=0;x+pos<=N;x++) {
			// front
			if(x>0 && (x-1>=M||T[x-1]==S[pos])) (dp[x-1][x+pos]+=dp[x][x+pos])%=mo;
			// back
			if(x+pos<N&&(x+pos>=M||T[x+pos]==S[pos])) (dp[x][x+pos+1]+=dp[x][x+pos])%=mo;
		}
	}
	ll ret=0;
	for(i=M;i<=N;i++) {
		ret+=dp[0][i];
	}
	cout<<ret%mo<<endl;
}

まとめ

先に真ん中の位置を決めてしまうのがポイント。