CODE THANKS FESTIVAL 2014 B : F - 太鼓ゲーム

まだ簡単。
http://code-thanks-festival-2014-b-open.contest.atcoder.jp/tasks/code_thanks_festival_14_qualb_f

問題

文字列X,S,Tがある。
Xを幾つかのS,Tの連結で表す方法は何通りあるか答えよ。

解法

Xのうち先頭i文字をS,Tの連結で表す方法をdp[i]とする。

• X[i-|T|+1,..,i]==Sならdp[i]+=dp[i-|S|]
• X[i-|T|+1,..,i]==Tならdp[i]+=dp[i-|T|]

とする単純なDPで済む。

Xの部分文字列とS,Tの判定をRollingHashで行えば全体でO(|X|)。
愚直に判定してもO(|X|*(|S|+|T|))なので、1000文字以内なら余裕で間に合う。

string X,S,T;
ll dp[1003];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>X>>S>>T;
	
	dp[0]=1;
	FOR(i,X.size()) {
		if(i>=S.size()-1 && S==X.substr(i-(S.size()-1),S.size())) dp[i+1]+=dp[i-(S.size()-1)];
		if(i>=T.size()-1 && T==X.substr(i-(T.size()-1),T.size())) dp[i+1]+=dp[i-(T.size()-1)];
		dp[i+1]%=mo;
	}
	cout<<dp[X.size()]<<endl;
}

まとめ

もうF問題だし、|X|≦10^5位にしてRollingHash等前提でも良いぐらいの難易度だと思うけどな。