#include using namespace std; #define LOCAL #pragma region Macros typedef long long ll; #define ALL(x) (x).begin(),(x).end() const long long MOD=1000000007; // const long long MOD=998244353; const int INF=1e9; const long long IINF=1e18; const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; const char dir[4]={'D','R','U','L'}; template istream &operator>>(istream &is,vector &v){ for (T &x:v) is >> x; return is; } template ostream &operator<<(ostream &os,const vector &v){ for (int i=0;i ostream &operator<<(ostream &os,const pair &p){ os << '(' << p.first << ',' << p.second << ')'; return os; } template ostream &operator<<(ostream &os,const map &m){ os << '{'; for (auto itr=m.begin();itr!=m.end();++itr){ os << '(' << itr->first << ',' << itr->second << ')'; if (++itr!=m.end()) os << ','; --itr; } os << '}'; return os; } template ostream &operator<<(ostream &os,const set &s){ os << '{'; for (auto itr=s.begin();itr!=s.end();++itr){ os << *itr; if (++itr!=s.end()) os << ','; --itr; } os << '}'; return os; } void debug_out(){cerr << '\n';} template void debug_out(Head&& head,Tail&&... tail){ cerr << head; if (sizeof...(Tail)>0) cerr << ", "; debug_out(move(tail)...); } #ifdef LOCAL #define debug(...) cerr << " ";\ cerr << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << '\n';\ cerr << " ";\ debug_out(__VA_ARGS__) #else #define debug(...) 42 #endif template T gcd(T x,T y){return y!=0?gcd(y,x%y):x;} template T lcm(T x,T y){return x/gcd(x,y)*y;} template inline bool chmin(T1 &a,T2 b){ if (a>b){a=b; return true;} return false; } template inline bool chmax(T1 &a,T2 b){ if (a struct Trie{ struct TrieNode{ char c; int dep; vector nxt,idxs; TrieNode(char c,int dep):c(c),dep(dep),nxt(char_size,-1){} }; vector Nodes; function ctoi; Trie(function ctoi):ctoi(ctoi){ Nodes.emplace_back('$',0); } inline int &next(int node,int c){ return Nodes[node].nxt[c]; } inline int &next(int node,char c){ return next(node,ctoi(c)); } void add(const string &s,int x=0){ int node=0; for (int i=0;i void query(const string &s,const F &f,int l){ int node=0; for (int i=l;i idxs(int node){return Nodes[node].idxs;} }; template struct AhoCorasick:Trie{ using Trie::Trie; using Trie::next; using Trie::ctoi; const int FAIL=char_size; vector cnt; void build(bool heavy=true){ auto &Nodes=this->Nodes; cnt.resize(Nodes.size()); for (int i=0;i que; for (int i=0;i<=char_size;++i){ if (~next(0,i)){ next(next(0,i),FAIL)=0; que.emplace(next(0,i)); } else next(0,i)=0; } while (!que.empty()){ auto &node=Nodes[que.front()]; int fail=node.nxt[FAIL]; cnt[que.front()]+=cnt[fail]; que.pop(); for (int i=0;i w; set_union(u.begin(),u.end(),v.begin(),v.end(),back_inserter(w)); u=w; } que.emplace(node.nxt[i]); } else node.nxt[i]=Nodes[fail].nxt[i]; } } } map match(const string &s,int now=0){ auto &Nodes=this->Nodes; map res; for (auto c:s){ now=next(now,ctoi(c)); for (auto &id:Nodes[now].idxs) ++res[id]; } return res; } int move(const char &c,int now){ while (next(now,ctoi(c))<0) now=next(now,FAIL); return next(now,ctoi(c)); } pair move(const string &s,int now=0){ long long res=0; for (auto &c:s){ int nxt=move(c,now); res+=cnt[nxt]; now=nxt; } return {res,now}; } int count(int node){return cnt[node];} }; int main(){ cin.tie(0); ios::sync_with_stdio(false); string S; int M; cin >> S >> M; AhoCorasick<26> AHO([](char c){return c-'A';}); for (;M--;){ string C; cin >> C; AHO.add(C); } AHO.build(); cout << AHO.move(S).first << '\n'; }