#include #define REP(i,n) for (long long i=0;i<(n);i++) #define FOR(i,a,b) for (long long i=(a);i<(b);i++) #define RREP(i,n) for(long long i=n;i>=0;i--) #define RFOR(i,a,b) for(long long i=(a);i>(b);i--) #define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl #define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl #define dump(x) cerr << #x << " => " << (x) << endl #define dumpP(p) cerr << "( " << p.first << " , " << p.second << " )" << ends #define SORT(c) sort((c).begin(),(c).end()) #define MIN(vec) *min_element(vec.begin(), vec.end()) #define MAX(vec) *max_element(vec.begin(), vec.end()) #define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end()) //ソートの必要あり #define IN(n,m) (!(m.find(n) == m.end())) #define ENUM(m) for (auto itr = m.begin(); itr != m.end(); ++itr) #define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> " << itr->second << endl; } #define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin()) #define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin()) #define ROUND(N) setprecision(N) #define ROUND_PRINT(N,val) cout << fixed;cout << setprecision(N) << val << endl #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(), (a).rend() #define INARR(h,w,x,y) (0 <= y && y < h && 0 <= x && x < w) #define EQ(a,b) (abs(a - b) < 1e-10) using namespace std; //#define CHAR_MAX 127 struct Trie { bool leaf; int sz = 0; // node[0] is for failure link Trie* node[CHAR_MAX]; vector accept; Trie() { leaf = false; for(int i=0; isz); for(int i=0; inode[c]) r->node[c] = new Trie; r = r->node[c]; } r->accept.push_back(dic_size-1); r->leaf = true; } }; class AhoCorasick { private: Trie trie; void updateFailure() { Trie* root = ≜ queue que; for (int c = 1;c < CHAR_MAX;c++) { if (root->node[c]) { root->node[c]->node[0] = root; que.push(root->node[c]); } else root->node[c] = root; } while (!que.empty()) { Trie *t = que.front();que.pop(); for (int c = 1;c < CHAR_MAX;c++) { if ( t->node[c]) { que.push(t->node[c]); Trie *r = t->node[0]; while (!r->node[c]) r = r->node[0]; t->node[c]->node[0] = r->node[c]; t->node[c]->accept.insert(t->node[c]->accept.end(), r->node[c]->accept.begin(), r->node[c]->accept.end()); } } } } public: AhoCorasick(const vector &r) { for (int i = 0;i < r.size();i++) trie.insert(r[i]); updateFailure(); } int match(string &target,vector &result) { Trie* v = ≜ int count = 0; for (int i = 0;i < target.size();i++) { char c = target[i]; while (! v->node[c]) { v = v->node[0]; } v = v->node[c]; for (int j = 0; j < v->accept.size(); ++j) result[v->accept[j]]++; count += (v->accept.size()); } return count; } }; int main(void) { cin.tie(0); ios::sync_with_stdio(false); long M; string S; cin >> S >> M; vector C(M); REP(i,M) cin >> C[i]; AhoCorasick ac(C); vector result(M); cout << ac.match(S,result) << endl; }