#include "bits/stdc++.h" #define REP(i,num) for(ll i=0;i<(num);++i) #define FOR(i,c,num) for(ll (i)=(c);(i)<(num);++(i)) #define LOOP(i) while(i--) #define ALL(c) c.begin(),c.end() #define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<& lhs,const pair& rhs){return lhs.c comp rhs.c;} using namespace std; using ll = long long; using vll = vector; using vvll = vector>; constexpr ll atcoder_mod = 1e9+7; template T in(){ T x; cin >> x; return (x); } template> C vecin(int N){ C x(N);REP(i,N){ x[i]=in(); }return x; } void vout(){ cout << endl; } template void vout(Head&& h,Tail&&... t){ cout << ' ' << h;vout(forward(t)...); } void out(){ cout << endl; } template void out(Head&& h,Tail&&... t){ cout << h;vout(forward(t)...); } template bool chmax(T& a,T b){ if(a bool chmin(T& a,T b){ if(a>b){ a=b;return true; }return false; } class SuffixArray{ vector InducedSort(vector& str,int char_num,vector& type,vector& lms){ int N=str.size(); vector SA(N,-1),bin(char_num+1,0); REP(i,N) bin[str[i]+1]++; REP(i,char_num) bin[i+1] += bin[i]; map count; for(int i=lms.size()-1;i>=0;i--){ int ch = str[lms[i]]; SA[bin[ch+1]-1-count[ch]] = lms[i]; count[ch]++; } count.clear(); REP(i,N){ if(SA[i]>0 && type[SA[i]-1]!=0){ int ch = str[SA[i]-1]; SA[bin[ch]+count[ch]] = SA[i]-1; count[ch]++; } } count.clear(); for(int i=N-1;i>=0;i--){ if(SA[i]>0 && type[SA[i]-1]!=1){ int ch = str[SA[i]-1]; SA[bin[ch+1]-1-count[ch]] = SA[i]-1; count[ch]++; } } return SA; } vector SAIS(vector str,int char_num){ constexpr int S=0,L=1; if(str.size()==1){ vector ret(1,0); return ret; } int N=str.size(); vector type(N); type[N-1] = S; for(int i=N-2;i>=0;i--){ if(str[i]str[i+1]) type[i] = L; else type[i] = type[i+1]; } auto isLMS = [&](int i){return (i>0 && type[i-1]==L && type[i]==S);}; vector lms; REP(i,N){ if(isLMS(i)) lms.push_back(i); } auto SA = InducedSort(str,char_num,type,lms); vector newSA; REP(i,N){ if(isLMS(SA[i])) newSA.push_back(SA[i]); } swap(SA,newSA); map nums; int num = 0; nums[SA[0]] = num; for(int i=0,ei=SA.size()-1;i0 && (isLMS(left+d) || isLMS(right+d))){ break; } } if(diff) num++; nums[right] = num; } vector new_lms; for(auto& x:nums) new_lms.push_back(x.second); if(num+1 Construct(int char_num){ int N=S.size(); vector V(N); REP(i,N) V[i] = S[i]; V.push_back(0); return SAIS(V,char_num); } using Comp = bool (*)(string_view,string); vector::iterator binary_search(const string& T,Comp comp){ string_view SV(S); int N=T.size(); auto left=suffix.begin(),right=suffix.end(); auto middle=left+distance(left,right)/2; while(distance(left,right)>1){ auto SSV = SV.substr(*middle,min(N,SN-(*middle))); if(comp(SSV,T)){ left = middle; middle=left+distance(left,right)/2; } else{ right = middle; middle=left+distance(left,right)/2; } } return right; } vector::iterator lower_bound(const string& T){ return binary_search(T,[](string_view sv,string s){return sv::iterator upper_bound(const string& T){ return binary_search(T,[](string_view sv,string s){return sv<=s;}); } public: SuffixArray(const string& str,int char_num):S(str),SV(str){ suffix = Construct(char_num); SN = suffix.size(); } bool Search(const string& T){ auto res = lower_bound(T); int N=T.size(); return ((res!=suffix.end()) && (SV.substr(*res,min(N,SN-(*res)))<=T)); } ll Count(const string& T){ auto first = lower_bound(T); auto last = upper_bound(T); return distance(first,last); } private: string S; string_view SV; vector suffix; int SN; }; int main(){ cin.tie(0); ios::sync_with_stdio(false); cout<(); SuffixArray SA(S,256); auto M=in(); ll A=0; LOOP(M){ string C=in(); A += SA.Count(C); } return 0; }