#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], b[10][26]; 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 algorithm 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 && k + z[n-1-k] < j; k++) z[i-k] = z[n-1-k]; i -= k; j -= k; } // boyer moore REP (i,n) a[i] = 0; int not_found = n; REP (i,n-1) { a[n-1-z[i]] = n-1-i; if (i + 1 == z[i]) not_found = n-1-i; } REP (i,n-1) if (a[i] == 0) a[i] = not_found; a[n-1] = 1; REP (i,n) REP (j,26) b[i][j] = i+1; REP (i,n) b[i][c[i]-'A'] = 0; REP (i,n-1) REP (j,26) b[i+1][j] = min(b[i][j]+1,b[i+1][j]); 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 += max(a[j],b[j][s[i+j]-'A']); } } } cout << ans << endl; return 0; }