文字列検索 [yukicoder 430]

問題

http://yukicoder.me/problems/no/430

文字列Sがある。
M個の文字列C[i]がある。
文字列Sの部分文字列としてC[i]が何通りあるかをM個の文字列全て調べて、その総和を答える。

1 <= |S| <= 5*10^4
1 <= M <= 5 * 10^3
1 <= |C[i]| <= 10

考察

1. とりあえず文字列なんでローリングハッシュかな？
2. ローリングハッシュ使って愚直に書く
3. だめだった

4. |C[i]|の条件に特徴がある
5. Sの長さ10以下の部分文字列を全て列挙することを考えると5*10^5通りを超えない
6. これなら全部数えることができるので、予め全ての部分文字列をチェックして数えておく
7. 各C[i]ではそれを持ってきて総和を取るだけ

実装

http://yukicoder.me/submissions/121023

string S;
int M;
string C[5010];
map<string, int> cnt;
//-----------------------------------------------------------------
int main() {
	cin >> S >> M;
	rep(i, 0, M) cin >> C[i];

	int N = S.length();
	rep(i, 0, N) {
		string s = "";

		rep(len, 1, 11) {
			int j = i - len + 1;
			if (j < 0) break;
			s = S[j] + s;
			cnt[s]++;
		}
	}

	int ans = 0;
	rep(i, 0, M) ans += cnt[C[i]];
	cout << ans << endl;
}