#pragma GCC optimize("O3") #pragma GCC target("avx") #include #include #include #include #include using namespace std; struct SAComp{ const int h,*g; SAComp(const int h, const int* g) : h(h), g(g) {} bool operator()(const int a, const int b){ return a == b ? false : g[a] != g[b] ? g[a] < g[b] : g[a+h] < g[b+h]; } }; vector buildSA(const string &t){ int n=t.size(); int g[n],b[n]; vectorsuff(n); for(int i=0;i>s; s+='$'; int n=s.size(); vectorsuff=buildSA(s); vector>sorted(n); for(int i=0;i>T;T--;){ string q; cin>>q; int start=0,stop=n,idx=q.size()-1; for(;idx>=0;idx--){ pair ql={q[idx],start},qr={q[idx],stop}; start=lower_bound(sorted.begin(),sorted.end(),ql)-sorted.begin(); stop=lower_bound(sorted.begin(),sorted.end(),qr)-sorted.begin(); if(start==stop)break; } if(idx<0){ R+=stop-start; //{vectorv;for(;start