#include #include #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 struct Aho { vector> states; vector fail_path; vector> matched; Aho(vector dict) { states.push_back({}); for (auto s: dict) { int now = 0; for (auto c: s) { if (!states[now].count(c)) { states[now][c] = states.size(); states.push_back({}); } now = states[now][c]; } matched.resize(states.size()); matched[now].insert(s); } fail_path.resize(states.size()); queue q; q.push(0); while (!q.empty()) { auto now = q.front(); q.pop(); for (auto p: states[now]) { char c = p.first; int next = p.second; q.push(next); if (now == 0) continue; int fail = fail_path[now]; while (fail > 0 && !states[fail].count(c)) fail = fail_path[fail]; if (states[fail].count(c)) { int x = states[fail][c]; fail_path[next] = x; matched[next].insert(matched[x].begin(),matched[x].end()); } } } } int match(string s) { int matches; int now = 0; for (auto c: s) { while (now > 0 && !states[now].count(c)) now = fail_path[now]; if (states[now].count(c)) { now = states[now][c]; matches += matched[now].size(); } } return matches; } }; int main(void) { int i, j, k, m; string s; cin >> s >> m; vector dict; while (m--) { string t; cin >> t; dict.push_back(t); } Aho aho = Aho(dict); cout << aho.match(s) << endl; return 0; }