#include using namespace std; using VI = vector; using VVI = vector; using PII = pair; using LL = long long; using VL = vector; using VVL = vector; using PLL = pair; using VS = vector; #define ALL(a) begin((a)),end((a)) #define RALL(a) (a).rbegin(), (a).rend() #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(a) int((a).size()) #define SORT(c) sort(ALL((c))) #define RSORT(c) sort(RALL((c))) #define UNIQ(c) (c).erase(unique(ALL((c))), end((c))) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define FF first #define SS second #define DUMP(x) cout<<#x<<":"<<(x)< istream& operator>>(istream& is, pair& p){ return is >> p.FF >> p.SS; } template istream& operator>>(istream& is, vector& xs){ for(auto& x: xs) is >> x; return is; } template ostream& operator<<(ostream& os, const pair& p){ return os << p.FF << " " << p.SS; } template ostream& operator<<(ostream& os, const vector& xs){ for(unsigned int i=0;i void maxi(T& x, T y){ if(x < y) x = y; } template void mini(T& x, T y){ if(x > y) x = y; } const double EPS = 1e-10; const double PI = acos(-1.0); const LL MOD = 1e9+7; struct Aho{ // failure link is slways 0. static const int FAIL = 0; static const int SIZE = 26 + 1; static int idx(char c){ return c-'A' + 1; } struct Node{ vector chd; vector accept; Node(){ chd.assign(SIZE, nullptr); } //~Node(){ FOR(i,1,SIZE){ delete chd[i]; chd[i] = nullptr; } } }; Node* root; int kind; Aho(){ root = nullptr; } void build(const vector& vs){ //delete root; root = new Node(); kind = vs.size(); for(int i=0;ichd[ix]) crt->chd[ix] = new Node(); crt = crt->chd[ix]; } crt->accept.push_back(i); } queue q; for(int i=1;ichd[i]){ root->chd[i]->chd[FAIL] = root; q.push(root->chd[i]); } else root->chd[i] = root; while(!q.empty()){ Node* t = q.front(); q.pop(); for(int i=1;ichd[i]){ q.push(t->chd[i]); Node* p = t->chd[FAIL]; while(!p->chd[i]) p = p->chd[FAIL]; t->chd[i]->chd[FAIL] = p->chd[i]; t->chd[i]->accept.insert(t->chd[i]->accept.end(), p->chd[i]->accept.begin(), p->chd[i]->accept.end()); } } } /** * require: |res| == kind */ void match(const string& s, vector& res){ Node* crt = root; for(char c: s){ int ix = idx(c); while(!crt->chd[ix]) crt = crt->chd[FAIL]; crt = crt->chd[ix]; for(int id: crt->accept) ++res[id]; } } }; int main(){ cin.tie(0); ios_base::sync_with_stdio(false); string S; cin >> S; int M; cin >> M; VS vs(M); REP(i,M) cin >> vs[i]; Aho aho; aho.build(vs); VI res(M); aho.match(S, res); cout << accumulate(ALL(res), 0) << endl; return 0; }