TopCoder SRM 541 Div1 Medium AkariDaisukiDiv1

問題

文字列A, B, Cが与えられたとき、
文字列xに対する操作fを、f(x) = A + x + B + x + Cとする。
（+は文字列の結合を表す）

fをn回適用する操作（f(f...(f(f(x)))...))をf^nと書く。
f^k(x)に、文字列Fが何回出現するかを求めよ。

制約条件

A, B, C, Fの長さは50以下
k≦1000万

方針

文字列の左端、右端が何か、端以外でFが何回出てくるかを持つ。

fを一回適用するたびに、
端以外での個数は2倍になり、
左端、中央、右端の部分で新たにFが出来る場合があるので、
その個数を足す。

その後左端、右端を更新する。
という風にして数えればいい。

愚直にやるとTLEなので、
左端、右端の文字列をメモ化して、同じ文字列が出てきたら、
後はループするのでまとめて処理してやると数百msで通る。

ソースコード

const int mod = (int)1e9 + 7;
int count(const string &a, const string &b){
	int res = 0;
	rep(i, (int)a.size() - (int)b.size() + 1){
		if(a.substr(i, b.size()) == b) res++;
	}
	return res;
}

class AkariDaisukiDiv1 {
	public:
	int countF(string Waai, string Akari, string Daisuki, string S, string F, int k) 
	{
		string s = Waai + S + Akari + S + Daisuki;
		
		k--;
		while(k > 0 && s.size() < F.size() + 50){
			s = Waai + s + Akari + s + Daisuki;
			k--;
		}
		
		int ans = count(s, F);
		if(k == 0) return ans;
		
		string suf = s.substr(s.size() - F.size() + 1);
		string pre = s.substr(0, F.size() - 1);
		
		map<pair<string, string>, int> memo;
		map<int, int> memo2;
		
		rep(it, k){
			if(memo.count(mp(pre, suf))){
				int prev = memo[mp(pre, suf)];
				int len = it - prev;
				while(it < k){
					ans = ans * 2 + memo2[(it - prev) % len + prev];
					ans %= mod;
					it++;
				}
				break;
			}
			memo[mp(pre, suf)] = it;
			
			string npre = Waai + pre;
			string nsuf = suf + Daisuki;
			
			int diff = count(nsuf, F) + count(npre, F) + count(suf + Akari + pre, F);
			memo2[it] = diff;
			
			ans = ans * 2 + diff;
			ans %= mod;
			
			suf = nsuf.substr(nsuf.size() - F.size() + 1);
			pre = npre.substr(0, F.size() - 1);
		}
		
		return ans;
	}
};