#include #include #include using namespace std; // Z Algorithm // 最長共通prefix長列を返す // 計算量: O(|S|) // アルゴリズム // k > r -> それまで計算したzの結果は利用できず、ナイーブに計算する // z[k-l] < r-k+1 -> S[0:r-l] == S[l:r] であり、kがすっぽり入っているので一発 // z[k-l] >= r-k+1 -> S[0:r-k+1] == S[k:r] であるので、追加分を計算する vector ZAlgorithm(const string& S) { int N = S.size(); vector z(N); z[0] = -1; int l = 0, r = 0; for (int k = 1; k < N; k++) { if (k > r) { l = k; r = k - 1; z[k] = 0; for (int i = 0; k + i < N; i++) { if (S[i] == S[k + i]) { z[k]++; r++; } else { break; } } } else if (z[k - l] < r - k + 1) { z[k] = z[k - l]; } else if (z[k - l] >= r - k + 1) { l = k; z[k] = r - k + 1; for (int i = r - k + 1; k + i < N; i++) { if (S[i] == S[k + i]) { z[k]++; r++; } else { break; } } } } return z; } // verified // https://yukicoder.me/problems/no/430 void yuki430() { string S, C; int M; cin >> S >> M; int ans = 0; while (M--) { cin >> C; vector Z = ZAlgorithm(C + S); for (int i = C.size(); i < Z.size(); i++) { if (Z[i] >= C.size()) ans++; } } cout << ans << "\n"; } int main() { yuki430(); return 0; }