TopCoder SRM 541 Div1 Medium: AkariDaisukiDiv1

解法

最初のうちは愚直に繰り返すが、ある程度繰り返すと先頭と末尾で常に同じ文字列が生成されるようになるので、あとは足し算を繰り返していくだけで良い。

コード

public class AkariDaisukiDiv1 {

	private final int MOD = 1000000007;

	public int countF(String W, String A, String D, String S, String F, int k) {
		long ans = cnt(S, F);
		String prefix = null, suffix = null;

		long cntWaai = 0, cntAkari = 0, cntDaiuki = 0;
		for (int i = 0; i < k; ++i) {
			// SがFより短い時は愚直にやる
			if (i == 0 || S.length() <= F.length()) {
				S = new StringBuilder(W).append(S).append(A).append(S)
						.append(D).toString();
				ans = cnt(S, F);
			} else {
				// suffixとprefixが変わりそうなときだけ文字列処理
				if (i <= F.length() + 2) {
					/*
					 * 文字列処理は重いので数を少なめにしたい。Fの文字数よりも多く繰り返せばW、A、Dが何であっても,
					 * prefixとsuffixは同じになる
					 */
					if (prefix == null) {
						prefix = S.substring(0, F.length() - 1);
						suffix = S.substring(S.length() - (F.length() - 1));
					}

					cntWaai = cnt(W + prefix, F);
					cntAkari = cnt(suffix + A + prefix, F);
					cntDaiuki = cnt(suffix + D, F);

					prefix = (W + prefix).substring(0, F.length() - 1);
					suffix = (suffix + D);
					suffix = suffix.substring(suffix.length() - F.length() + 1);
				}

				ans = (2 * ans + cntWaai + cntAkari + cntDaiuki) % MOD;
			}
		}

		return (int) ans;
	}
	private int cnt(String string, String f) {
		int res = 0;
		int g = string.length() - f.length();
		for (int i = 0; i <= g; ++i) {
			if (string.startsWith(f, i)) {
				res++;
			}
		}
		return res;
	}

}