#include<bits/stdc++.h> 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 vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} template<class A,class B> ostream& operator<<(ostream& ost,const pair<A,B>&p){ ost<<"{"<<p.first<<","<<p.second<<"}"; return ost; } template<class T> ostream& operator<<(ostream& ost,const vector<T>&v){ ost<<"{"; for(int i=0;i<v.size();i++){ if(i)ost<<","; ost<<v[i]; } ost<<"}"; return ost; } struct AhoCorasick{ static const int OFF=(int)('A'); // c \in [OFF,OFF+LEN) static const int LEN=26; struct Node{ int nex[LEN]; int failink; vector<int>suflist; Node():failink(0){memset(nex,-1,sizeof(nex));} }; vector<Node>nds; 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(){ queue<int>que; for(int i=0;i<LEN;i++){ if(nds[0].nex[i]==-1)nds[0].nex[i]=0; else que.push(nds[0].nex[i]); } while(que.size()){ int k=que.front(); que.pop(); for(int i=0;i<LEN;i++){ if(nds[k].nex[i]==-1)continue; int nx=nds[k].nex[i]; nds[nx].failink=process(nds[k].failink,i+OFF); vector<int>&curlist=nds[nds[nx].failink].suflist; vector<int>&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<<ans<<endl; return 0; }