Codeforces #187 Div1. B. Sereja and Periods

本番TLEしてしまった問題。
http://codeforces.com/contest/314/problem/B

問題

文字列aをb回繰り返して生成できる文字列から文字を抜いていった場合、文字列cをd回繰り返した文字列を最大何個作れるか答えよ。

解法

c中にaにない文字があれば、cは1個も作れないので終了。

そうでない場合、今cのi文字目まで来た状態で、a中の文字を順に見て、cのi+1文字目と一致する文字があればiをインクリメントする、として、c中何文字分とれるかを事前に計算する。
この処理はO(len(a)・len(c))。

後は上記状態遷移をb回繰り返し、c中の文字列何文字分とれるかを求めて、len(c)×dで割るだけ。

int B,D;
string A,C;
int num[101],AL,CL;

void solve() {
	int f,r,i,j,k,l, x,y;

	cin>>B>>D>>A>>C;
	AL=A.size();
	CL=C.size();

	FOR(x,CL) {
		FOR(y,AL) if(A[y]==C[(x+num[x])%CL]) num[x]++;
		if(num[x]==0) return _P("0\n");
	}
	
	ll re=0;
	int po=0;
	FOR(i,B) {
		re+=num[po];
		po=(po+num[po])%CL;
	}

	cout << re/(D*CL) << endl;
	return;
}

まとめ

これ、bとd小さすぎないかな？
本当はdoublingとか期待してたのでは…と思ってしまう。