#include #define FOR(v, a, b) for(int v = (a); v < (b); ++v) #define FORE(v, a, b) for(int v = (a); v <= (b); ++v) #define REP(v, n) FOR(v, 0, n) #define REPE(v, n) FORE(v, 0, n) #define REV(v, a, b) for(int v = (a); v >= (b); --v) #define ALL(x) (x).begin(), (x).end() #define RALL(x) (x).rbegin(), (x).rend() #define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it) #define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it) #define EXIST(c,x) ((c).find(x) != (c).end()) #define LLI long long int #define fst first #define snd second #define popcount __builtin_popcount #ifdef DEBUG #include #else #define dump(x) ((void)0) #endif #define gcd __gcd using namespace std; template constexpr T lcm(T m, T n){return m/gcd(m,n)*n;} template void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost< istream& operator>>(istream &is, vector &v){for(auto &a : v) is >> a; return is;} template istream& operator>>(istream &is, pair &p){is >> p.first >> p.second; return is;} template bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);} template bool chmax(T &a, const U &b){return (a void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);} class AhoCorasick{ public: int n; vector> trie; vector failure_edge; vector dict; vector> dict_index; AhoCorasick(): n(1), trie(1), failure_edge(1){ } void add(const string &s){ dict.push_back(s); int cur = 0; REP(i,(int)s.size()){ char c = s[i]; if(EXIST(trie[cur], c)){ cur = trie[cur][c]; }else{ ++n; trie.resize(n); trie[cur][c] = n-1; cur = trie[cur][c]; } } dict_index.resize(n); dict_index[cur].push_back(dict.size()-1); } void construct_failure_link(){ failure_edge.resize(n); queue dq; dq.push(0); while(not dq.empty()){ int cur = dq.front(); dq.pop(); for(auto &kv : trie[cur]){ char c = kv.fst; int next = kv.snd; if(cur == 0){ failure_edge[next] = 0; }else{ int i = failure_edge[cur]; int j = 0; while(1){ if(EXIST(trie[i], c)){ j = trie[i][c]; break; }else{ if(i == 0) break; i = failure_edge[i]; } } failure_edge[next] = j; for(auto k : dict_index[failure_edge[next]]){ dict_index[next].push_back(k); } } dq.push(next); } } } vector> find(const string &s){ vector> ret; int cur = 0; REP(i,(int)s.size()){ char c = s[i]; while(cur != 0 and not EXIST(trie[cur], c)){ cur = failure_edge[cur]; } cur = trie[cur][c]; for(auto j : dict_index[cur]){ ret.push_back({i, j}); } } return ret; } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); string S; int M; while(cin >> S >> M){ vector C(M); cin >> C; AhoCorasick ac; REP(i,M){ ac.add(C[i]); } ac.construct_failure_link(); auto ret = ac.find(S); dump(ret); int ans = ret.size(); cout << ans << endl; } return 0; }