#include #include #include #include #include #include #include #include using namespace std; #define GET_ARG(a,b,c,F,...) F #define REP3(i,s,e) for (i = s; i <= e; i++) #define REP2(i,n) REP3 (i,0,(int)(n)-1) #define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__) #define RREP3(i,s,e) for (i = s; i >= e; i--) #define RREP2(i,n) RREP3 (i,(int)(n)-1,0) #define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__) #define DEBUG(x) cerr << #x ": " << x << endl int z[10], a[10]; int main(void) { int m; string s; cin >> s >> m; int ans = 0; while (m--) { string c; cin >> c; int i, j, k, n = c.size(); if (n > s.size()) continue; z[n-1] = n; for (i = n-2, j = 0; i >= 0; ) { for (; i-j >= 0 && c[i-j] == c[n-1-j]; j++); z[i] = j; if (j == 0) { i--; continue; } for (k = 1; i-k >= 0 && n - 1 - k - z[n-1-k] > j; k++) z[i-k] = z[n-1-k]; i -= k; j -= k; } REP (i,n) a[i] = 0; REP (i,n-1) a[n-1-z[i]] = n-1-i; a[n-1] = 1; RREP (i,n-1) if (a[i] == 0) a[i] = a[i+1]; for (i = 0; i <= s.size() - c.size(); ) { for (j = c.size()-1; j >= 0; j--) { if (s[i+j] != c[j]) break; } if (j < 0) { ans++; i += a[0]; } else { i += a[j]; } } } cout << ans << endl; return 0; }