読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 519 Div1 Medium: RequiredSubstrings

解法

桁DPの強いバージョン。深さ優先探索で1文字ずつ足していった時に、C個の文字列を含む状態になるかどうかをメモ化して調べれば良い。文字列の後ろl文字がとwords[i]の前l文字と一致している時に、文字列に1文字cを追加したら何文字が一致するようになるかというのを保存しておく。

コード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class RequiredSubstrings {
	private final int MOD = (int) 1e9 + 9, MAX_L = 55;
	private String[] words;
	private int C, L, N;
	private int[][][] matches;
	private ArrayList<HashMap<Long, Integer>> dp;

	public int solve(String[] words, int C, int L) {
		this.words = words;
		this.C = C;
		this.L = L;

		N = words.length;
		matches = new int[N][MAX_L][26];
		dp = new ArrayList<>();
		for (int i = 0; i < MAX_L; i++) {
			dp.add(new HashMap<Long, Integer>());
		}

		/*
		 * words[i]から最初のl文字を切り出して適当な1文字cをつけた時, それがwords[i]とどのくらい一致するか調べておく
		 */
		for (int i = 0; i < N; i++) {
			for (int l = 0; l < words[i].length(); l++) {
				for (int c = 0; c < 26; c++) {
					String string = words[i].substring(0, l) + (char) (c + 'a');

					// words[i]の先端とstringの後端とは何文字一致するか
					for (int k = 0; k <= string.length(); k++) {
						String prefix = words[i].substring(0, k);
						String suffix = string.substring(string.length() - k);
						if (prefix.equals(suffix)) {
							matches[i][l][c] = k;
						}
					}
				}
			}

			Arrays.fill(matches[i][words[i].length()], words[i].length());
		}

		return dfs(0, new int[N]);
	}

	private int dfs(int pos, int[] nowMatch) {
		if (pos >= L) {
			int cnt = 0;
			for (int i = 0; i < N; i++) {
				if (nowMatch[i] == words[i].length()) {
					cnt++;
				}
			}
			if (cnt == C) {
				return 1;
			} else {
				return 0;
			}
		}

		long nowMatchKey = 0;
		for (int i = 0; i < N; i++) {
			nowMatchKey = nowMatchKey * MAX_L + nowMatch[i];
		}
		if (dp.get(pos).containsKey(nowMatchKey)) {
			return dp.get(pos).get(nowMatchKey);
		}

		long ans = 0;
		for (int c = 0; c < 26; c++) {
			/* いまの状態でcを足したらどうなるかを考える */
			int[] nextMatch = new int[N];
			for (int i = 0; i < N; i++) {
				nextMatch[i] = matches[i][nowMatch[i]][c];
			}
			ans = (ans + dfs(pos + 1, nextMatch)) % MOD;
		}
		dp.get(pos).put(nowMatchKey, (int) ans);
		return (int) ans;

	}
}