#pragma GCC optimize("Ofast","unroll-loops") #pragma comment(linker, "/stack:200000000") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include using namespace std::chrono; using namespace::std; //struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout< // #include // #include // #include // #include // #include // #include // #include // #include // using boost::math::tools::brent_find_minima; // #include // #include // namespace mp = boost::multiprecision; // typedef mp::number> cdouble; // typedef mp::cpp_int cint; // #include #include #include #include #include templateusing pbds=__gnu_pbds::tree,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; templateusing pbds_map=__gnu_pbds::tree,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; templateusing pqueue =__gnu_pbds::priority_queue,__gnu_pbds::rc_binomial_heap_tag>; typedef long long lint; typedef long long ll; typedef long double ldouble; typedef vector vec; typedef vector> mat; typedef vector>> mat3; typedef vector dvec; typedef vector> dmat; typedef vector>> dmat3; typedef vector svec; typedef vector> smat; typedef vector>> smat3; templateusing Vec=vector; templateusing Mat=vector>; templateusing Mat3=vector>>; templateusing Mat4=vector>>>; templateusing pvec=vector>; templateusing pmat=vector>>; templateusing pmat3=vector>>>; templateusing pmat4=vector>>>>; templateusing tvec=vector>; templateusing tmat=vector>>; templateusing tmat3=vector>>>; templateusing tmat4=vector>>>>; #define rep(i, n) for(lint i = 0; i < (lint)(n); i++) #define irep(i) for(lint i = 0;; i++) #define irepi(i,n) for(lint i = (n);; i++) #define rrep(i, n) for(lint i = (lint)(n-1); i >-1; i--) #define rrepi(i,a,b) for(lint i = (lint)(b-1); i >a-1; i--) #define repi(i,a,b) for(lint i=lint(a);ilint(b);i+=c) #define all(x) (x).begin(),(x).end() #define dist(x1,y1,x2,y2) (pow(pow(x2-x1,2)+pow(y2-y1,2),0.5)) //#define input(a,n) lint n;cin>>n;vectora(n);rep(i,n)cin>>a[i]; #define SUM(v) accumulate(all(v),0LL) #define INF (1LL<<60) #define IINF (1<<30) #define EPS (1e-10) #define LINF 9223372036854775807LL #define MOD 998244353LL //#define MOD 1000000007LL #define endl "\n" templateinline void numout(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<inline void numout2(T t){for(auto i:t)numout(i);} templateinline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<inline void output2(T t){for(auto i:t)output(i);} templateinline void _output(T t){bool f=0;for(int i=0;iinline void _output2(T t){for(int i=0;iT in(){return *istream_iterator(cin);} templateinline T gcd(T a,T b){return b?gcd(b,a%b):a;} templateinline T lcm(T a,T b){return a/gcd(a,b)*b;} templateinline T minq(T a,T b){return min(a,b);} templateinline T maxq(T a,T b){return max(a,b);} inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;} inline bool chmax(auto& s,const auto& t){bool res=s dx={-1,1,0,0,1,1,-1,-1}; const vector dy={0,0,-1,1,1,-1,1,-1}; class AhoCorasick{ struct node; using np=node*; constexpr static int num=26; constexpr static char base='A'; struct node{ np ch[num]; np link=nullptr; int val=0; node(){ rep(i,num)ch[i]=nullptr; } }; np root=new node(); np root_par=new node(); public: AhoCorasick(){ root->link=root_par; rep(i,num)root_par->ch[i]=root; } void insert(string v){ np t=root; int idx=0; while(idx<(lint)v.size()){ if(!t->ch[v[idx]-base])t->ch[v[idx]-base]=new node(); t=t->ch[v[idx]-base]; idx++; } t->val++; } void build(){ built=1; queueque; que.push(root); while(!que.empty()){ np t=que.front(); que.pop(); rep(i,num){ if(!t->ch[i])continue; if(t==root){ t->ch[i]->link=t; }else{ np s=t->link; while(!s->ch[i]){ s=s->link; } t->ch[i]->link=s->ch[i]; } que.push(t->ch[i]); } } } bool built=0; int count(string v){ if(!built){build();built=1;} np t=root; int idx=0; int res=0; while(idx<(int)v.size()){ while(!t->ch[v[idx]-base]){ if(t==root){ idx++; if(idx==(int)v.size())return res; }else{ t=t->link; } } t=t->ch[v[idx++]-base]; auto s=t; while(s!=root){ res+=s->val; s=s->link; } } return res; } int find_first(string v){ if(!built){build();built=1;} np t=root; int idx=0; int res=0; while(idx<(lint)v.size()){ while(!t->ch[v[idx]-base]){ if(t==root){ res++; idx++; if(idx==(lint)v.size())return -1; }else{ res++; t=t->link; } } t=t->ch[v[idx++]-base]; if(t->val>0)return res; } return -1; } }; int main(){ string s; cin>>s; lint q; cin>>q; AhoCorasick aho; rep(i,q){ string t; cin>>t; aho.insert(t); } cout<