#line 1 "test.cpp" #include #line 2 "/Library/kyopro-lib/lib/string/kmp.hpp" /** * @file manachar.hpp * @brief KMPアルゴリズムに関するコード。 * @details * * 文字列SとパターンPに対し、Pの出現位置をO(|P| + |S|)で列挙する。 */ #line 12 "/Library/kyopro-lib/lib/string/kmp.hpp" #line 14 "/Library/kyopro-lib/lib/string/kmp.hpp" using namespace std; // 参考:アルゴリズムイントロダクション第3版 namespace kmp_inner { std::vector compute_prefix_function_(const std::string &P) { const int m = P.size(); std::vector pi(m); pi[0] = -1; int k = -1; for (int q = 1; q < m; ++q) { while (k >= 0 && P[k + 1] != P[q]) { k = pi[k]; } if (P[k + 1] == P[q]) ++k; pi[q] = k; } return pi; } } // namespace kmp_inner std::vector kmp(const std::string &S, const std::string &P) { const int n = S.size(); const int m = P.size(); auto pi = kmp_inner::compute_prefix_function_(P); int q = -1; std::vector ret; for (int i = 0; i < n; ++i) { while (q >= 0 && P[q + 1] != S[i]) q = pi[q]; if (P[q + 1] == S[i]) ++q; if (q == m - 1) { ret.push_back(i - m + 1); q = pi[q]; } } return ret; } #line 4 "test.cpp" using namespace std; int main() { string S; int M; cin >> S >> M; int ans = 0; for (int i = 0; i < M; ++i) { string c; cin >> c; ans += kmp(S, c).size(); } cout << ans << endl; }