Codeforces 314B Sereja and Periods

問題

文字列aをb回繰り返すことを(a, b)と書く。
文字列a, cおよびそれらの繰り返し回数b, dが与えられる。
w = [a, b], q = [c, d]としたとき、
[q, p]がwの（必ずしも連続しない）部分文字列となるような最大の整数pを求めよ。

そのような正の整数pが存在しないときは0を出力せよ。

制約条件

a, cの長さは100以下
b, d≦10^7

方針

[a, b]の繰り返し文字列のうち、aをi回繰り返している時のj文字目を(i, j)と表すことにする。
決まったjから、cを一回マッチさせるごとに、iはいくつ進むかがわかれば、
iがbを超えるまでcをマッチさせ続けて、k回マッチができたとすると、
k / dが答えのpとなる。

毎回のマッチを全部計算すると、答えは10^9くらいになりうるのでTLE.
ここで同じjが出てきたら、前回同じjが出てきたときのiとkから、
差分を見てやって、(b - i) / ⊿i回のループは割り算ですっとばせるので、
すっとばしてやるようにすれば、間に合う。

ソースコード

int b, d;
map<int, pi> prev;
string a, c;

int main(){
	cin >> b >> d >> a >> c;
	int la = a.size(), lc = c.size();
	a += a;
	
	ll x = 0, y = 0, pa = 0;
	while(x < b){
		
		if(prev.count(pa)){
			ll px = prev[pa].first, py = prev[pa].second;
			ll t = (b - 1 - x) / (x - px);
			y += t * (y - py);
			x += t * (x - px);
		}
		else prev[pa] = mp(x, y);
		
		int i = 0;
		y++;
		for(; i < lc; i++){
			for(; pa < 2 * la && a[pa] != c[i]; pa++);
			if(pa == 2 * la){
				cout << 0 << endl;
				return 0;
			}
			if(++pa >= la){
				pa -= la;
				x++;
			}
		}
		//cerr<<x<<" "<<y<<" "<<pa<<endl;
	}
	if(pa) y--;
	cout << y / d << endl;
	
	return 0;
}