#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define REP(i,n) for(int i = 0; n > i; i++) #define MODU 33 #define Range(x,a,b) ((a) <= (x) && (x) <= (b)) #define POWT(x) ((x)*(x)) #define ALL(x) (x).begin(), (x).end() #define C_D(c) ((c) - '0') #define D_C(d) ((d) + '0') using namespace std; typedef vector Ivec; typedef pair pii; typedef long long int ll; #include void kmp_maketable(const char *key, int *table) { table[0] = -1; table[1] = 0; int i = 2, j = 0; while (i == 0 || key[i - 1]) { if (key[i - 1] == key[j]) { table[i++] = ++j; } else if (j>0) { j = table[j]; } else { table[i++] = 0; } } } int kmp_search(const char *str, const char *key, const int *table) { int cou = 0; int i = 0, j = 0; while (str[i]) { if (str[i] == key[j]) { if (!key[j + 1]) { cou++; } i++, ++j; } else if (j>0) { j = table[j]; } else { i++; } } return cou; } int main() { char str [500001]; int m; scanf("%s", str); scanf("%d", &m); ll cou = 0; REP(i, m) { char pat[101]; scanf("%s", pat); int table[500001]; kmp_maketable(pat,table); cou += kmp_search(str,pat,table); } printf("%lld\n",cou); return 0; }