#include using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define eb emplace_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vectorvint; typedef pairpint; typedef vectorvpint; templateinline void chmin(A &a,B b){if(a>b)a=b;} templateinline void chmax(A &a,B b){if(a ostream& operator<<(ostream& ost,const pair&p){ ost<<"{"< ostream& operator<<(ostream& ost,const vector&v){ ost<<"{"; for(int i=0;isuflist; Node():failink(0){memset(nex,-1,sizeof(nex));} }; vectornds; AhoCorasick():nds(1){} int process(int k,int c){ c-=OFF; while(nds[k].nex[c]==-1)k=nds[k].failink; return nds[k].nex[c]; } void add(const string &s,int id){ int k=0; for(auto c:s){ c-=OFF; if(nds[k].nex[c]==-1){ nds[k].nex[c]=nds.size(); nds.emplace_back(); } k=nds[k].nex[c]; } nds[k].suflist.push_back(id); } void build(){ queueque; for(int i=0;i&curlist=nds[nds[nx].failink].suflist; vector&nexlist=nds[nx].suflist; nexlist.insert(nexlist.end(),curlist.begin(),curlist.end()); que.push(nx); } } } }; signed main(){ string S;cin>>S; int M;cin>>M; AhoCorasick ac; rep(i,M){ string s;cin>>s; ac.add(s,i); } ac.build(); int ans=0; int k=0; for(auto c:S){ k=ac.process(k,c); ans+=ac.nds[k].suflist.size(); } cout<