// verification-helper: PROBLEM https://yukicoder.me/problems/1013 #include using namespace std; #define call_from_test template struct Trie{ struct Node{ char c; array nxt; vector idxs; int idx; Node(char c):c(c),idx(-1){fill(nxt.begin(),nxt.end(),-1);} }; using F = function; vector vs; F conv; Trie(F conv,char c='$'):conv(conv){vs.emplace_back(c);} Trie(char start,char c='$'):Trie([=](char a){return a-start;},c){} inline int &next(int i,int j){ return vs[i].nxt[j]; } void add(const string &s,int x){ int pos=0; for(int i=0;i<(int)s.size();i++){ int k=conv(s[i]); if(~next(pos,k)){ pos=next(pos,k); continue; } int npos=vs.size(); next(pos,k)=npos; vs.emplace_back(s[i]); pos=npos; } vs[pos].idx=x; vs[pos].idxs.emplace_back(x); } int find(const string &s){ int pos=0; for(int i=0;i<(int)s.size();i++){ int k=conv(s[i]); if(next(pos,k)<0) return -1; pos=next(pos,k); } return pos; } int move(int pos,char c){ assert(pos<(int)vs.size()); return pos<0?-1:next(pos,conv(c)); } int size(){return vs.size();} int idx(int pos){ return pos<0?-1:vs[pos].idx; } vector idxs(int pos){ return pos<0?vector():vs[pos].idxs; } }; template struct AhoCorasick : Trie{ using super = Trie; using super::super, super::next, super::size; using super::vs, super::conv; vector cnt; void build(){ int n=vs.size(); cnt.resize(n); for(int i=0;i que; for(int i=0;i<(int)X;i++){ if(~next(0,i)){ next(next(0,i),X)=0; que.emplace(next(0,i)); }else{ next(0,i)=0; } } while(!que.empty()){ auto &x=vs[que.front()]; int fail=x.nxt[X]; cnt[que.front()]+=cnt[fail]; que.pop(); for(int i=0;i<(int)X;i++){ int &nx=x.nxt[i]; if(nx<0){ nx=next(fail,i); continue; } que.emplace(nx); next(nx,X)=next(fail,i); if(heavy){ auto &idx=vs[nx].idxs; auto &idy=vs[next(fail,i)].idxs; vector idz; set_union(idx.begin(),idx.end(), idy.begin(),idy.end(), back_inserter(idz)); idx=idz; } } } } int count(int pos){ return cnt[pos]; } int match(string s){ int res=0,pos=0; for(auto &c:s){ pos=next(pos,conv(c)); res+=count(pos); } return res; } vector frequency(string s){ vector res(size(),0); int pos=0; for(auto &c:s){ pos=next(pos,conv(c)); res[pos]++; } for(int i=size()-1;i;i--) res[vs[i].nxt[X]]+=res[i]; return res; } }; #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); AhoCorasick<26, false> aho('A'); string s; cin>>s; int m; cin>>m; for(int i=0;i>c; aho.add(c,i); } aho.build(); cout<