#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define fs first #define sc second using namespace std; typedef long long ll; typedef unsigned int uint; typedef pair P; template class KMP{ vector a; T s; public: KMP(T s_arg): s(s_arg){ int n = s_arg.size(); a = vector(n+1, -1); // a[j+1]が[0, j]のboarderの最大の長さ } void constructBorderArray(){ int j = -1; for(int i = 0; i < s.size(); i++){ while(j >= 0 && s[i] != s[j]){ j = a[j]; } j++; if(s[i+1] == s[j]) a[i+1] = a[j]; else a[i+1] = j; } } /** * * @param x: sとマッチングさせる配列 * @return : マッチング位置 */ int search(T x, int pos=0){ int j = 0; for(int i = pos; i < x.size(); i++){ while(j >= 0 && x[i] != s[j]){ j = a[j]; } j++; if(j == s.size()){ return i - j + 1; } } return -1; } int count(T x, int pos=0){ int j = 0; int res = 0; for(int i = pos; i < x.size(); i++){ while(j >= 0 && x[i] != s[j]){ j = a[j]; } j++; if(j == s.size()){ res++; j = a[j]; } } return res; } }; int main(){ string s; cin >> s; int m; cin >> m; int res = 0; for(int i = 0; i < m; i++){ string t; cin >> t; KMP kmp(t); kmp.constructBorderArray(); res += kmp.count(s); } cout << res << endl; return 0; }