//#define _GLIBCXX_DEBUG #include using namespace std; #define endl '\n' #define lfs cout<= (ll)(n); i--) using ll = long long; using ld = long double; const ll MOD1 = 1e9+7; const ll MOD9 = 998244353; const ll INF = 1e18; using P = pair; templatebool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;} templatebool chmax(T1 &a,T2 b){if(avoid ans(bool x,T1 y,T2 z){if(x)cout<void debug(T &v,ll h,ll w,string sv=" "){for(ll i=0;ivoid debug(T &v,ll n,string sv=" "){if(n!=0)cout<vector>vec(ll x, ll y, T w){vector>v(x,vector(y,w));return v;} ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;} vectordx={1,-1,0,0,1,1,-1,-1};vectordy={0,0,1,-1,1,-1,1,-1}; templatevector make_v(size_t a,T b){return vector(a,b);} templateauto make_v(size_t a,Ts... ts){return vector(a,make_v(ts...));} templateostream &operator<<(ostream &os, const pair&p){return os << p.first << " " << p.second;} templateostream &operator<<(ostream &os, const vector &v){for(auto &z:v)os << z << " ";cout<<"|"; return os;} templatevoid rearrange(vector&ord, vector&v){ auto tmp = v; for(int i=0;ivoid rearrange(vector&ord,Head&& head, Tail&&... tail){ rearrange(ord, head); rearrange(ord, tail...); } //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); int popcount(ll x){return __builtin_popcountll(x);}; int poplow(ll x){return __builtin_ctzll(x);}; int pophigh(ll x){return 63 - __builtin_clzll(x);}; template< typename T = int > struct edge { int to; T cost; int id; edge() = default; edge(int to, T cost = 1, int id = 0):to(to), cost(cost), id(id){} operator int() const { return to; } }; template using Graph = vector>>; template Graph readGraph(int n,int m,int indexed=1,bool directed=false,bool weighted=false){ Graph ret(n); for(int es = 0; es < m; es++){ int u,v,w=1; cin>>u>>v;u-=indexed,v-=indexed; if(weighted)cin>>w; ret[u].emplace_back(v,w,es); if(!directed)ret[v].emplace_back(u,w,es); } return ret; } template Graph readParent(int n,int indexed=1,bool directed=true){ Graphret(n); for(int i=1;i>p; p-=indexed; ret[p].emplace_back(i); if(!directed)ret[i].emplace_back(p); } return ret; } template struct Trie{ struct Node{ arraynxt; vectoridx; int fail, len; Node(int l):fail(0), len(l){ fill(nxt.begin(), nxt.end(), -1); } }; vectordata; Trie(){ data.emplace_back(0); } int add(const string &s, int id=0){ int pos=0; for(int i=0;istr; void build_str(int pos=0,string s=""){ while(str.size()<=pos)str.push_back(""); str[pos]=s; for(int i=0;ique; for(int i=0;i aho_search(const string &s){ int now=0; vectorcnt(data.size()); for(int i=0;ivoid{ for(auto to:sg[k]){ f(f,to); cnt[k]+=cnt[to]; } }; dfs(dfs,0); return cnt; } Graph sg; void suffix_link(){ assert(sg.empty()); sg.resize(data.size()); for(int i=1;i; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll res=0,buf=0; bool judge = true; string s;cin>>s; ll m;cin>>m; vectorv(m); trie tri; rep(i,0,m){ string c;cin>>c; v[i]=tri.add(c,i); } //tri.build_str(); tri.build_Ahocorasick(); auto fre=tri.aho_search(s); rep(i,0,m){ res+=fre[v[i]]; } cout<