#include using namespace std; //construct SA by SA-IS O(N) #include #include struct SA{ string s; vectorsa; SA(const string&s_):s(s_) { sa=build(vector(s.begin(),s.end()),256); } vectorinduced_sort(const vector&S,const vector&id,const vector&SL,vectorlast) { vectorfirst(last); vectorret(id.size()); ret[0]=id[0]; for(int i=0;i=1&&!SL[id[i]-1]) { ret[first[S[id[i]-1]-1]++]=id[i]-1; } else if(ret[i]>=1&&!SL[ret[i]-1]) { ret[first[S[ret[i]-1]-1]++]=ret[i]-1; } } for(int i=id.size();i--;) { if(ret[i]>=1&&SL[ret[i]-1]) { ret[--last[S[ret[i]-1]]]=ret[i]-1; } } return ret; } vectorbuild(vectorS,int maxval) { if(S.size()<=1) { return S.empty()?(vector){0}:(vector){1,0}; } S.push_back(0); vectorcnt(maxval,0); vectorSL(S.size());//S=>true,L=>false for(int i=S.size();i--;) { cnt[S[i]]+=1; SL[i]=i+1==S.size()||S[i]last(cnt); vectorid(S.size()); vectoris_LMS(S.size()); int LMScnt=0; for(int i=1;i=0&&S[pre]==S[id[i]]) { int k; for(k=1;S[pre+k]==S[id[i]+k]&&!is_LMS[pre+k]&&!is_LMS[id[i]+k];k++); LMSsub-=S[pre+k]==S[id[i]+k]&&is_LMS[pre+k]&&is_LMS[id[i]+k]; } pre=id[i]; is_LMS[id[i]]=LMSsub++; } } vectornewstr(LMScnt); vectorrev(LMScnt); int counter=0; for(int i=0;isortedLMS=build(newstr,LMSsub); id.assign(S.size(),0); for(int i=1;i1) { int M=L+R>>1; if(s.compare(sa[M],t.size(),t)>=0)R=M; else L=M; } return R; } int upper_bound(const string&t)const { int L=-1,R=sa.size(); while(R-L>1) { int M=L+R>>1; if(s.compare(sa[M],t.size(),t)<=0)L=M; else R=M; } return R; } bool contain(const string&t)const { int id=lower_bound(t); return id>s; SA P(s); int N;cin>>N; int ans=0; for(int i=0;i>t; ans+=P.upper_bound(t)-P.lower_bound(t); } cout<