JAGSummerCamp12Day3B E : Substring
長さが異なれば、当然文字列が異なる。部分文字列の長さwと、開始位置の集合が与えられとき、長さwの部分文字列が何種類あるかを求められれば良い。接尾辞配列・LCP・RMQで共通接頭辞の長さが求められるので、それがw未満ならば異なる文字列。
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; template <class T>ostream &operator<<(ostream &o,const vector<T>&v) {o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;} // 接尾辞配列 class SuffixArrayCmp { vector<int>&R; int n,k; public: SuffixArrayCmp(vector<int>&R_,int n_,int k_):R(R_),n(n_),k(k_){} bool operator()(int i,int j){ if(R[i]!=R[j])return R[i]<R[j]; return(i+k<n?R[i+k]:-1)<(j+k<n?R[j+k]:-1);} }; vector<int>SuffixArray(string S) { int n=S.length(); vector<int>A(n),R(n); for(int i=0;i<n;i++) A[i]=i,R[i]=S[i]; for(int k=1;k<n;k*=2){ SuffixArrayCmp c(R,n,k); sort(A.begin(),A.end(),c); vector<int>T(n); T[A[0]]=0; for(int i=1; i<n; i++ ) T[A[i]]=T[A[i-1]]+(c(A[i-1],A[i])?1:0); R=T;} return A; } // 最長共通接頭辞 vector<int>LCP(string S,vector<int>A) { int n=(int)S.length(); vector<int>R(n),L(n-1); for(int i=0;i<n;i++)R[A[i]]=i; int h=0; for(int i=0;i<n;i++)if(R[i]>0){ if(h>0)h--; int j=A[R[i]-1]; for(;i+h<n&&j+h<n;h++) if(S[i+h]!=S[j+h])break; L[R[i]-1]=h;} return L; } // RMQ class RMQ { int n; vector<int>A; const static int M=0x7fffffff; int q(int a,int b,int k,int l,int r){ if(r<=a||b<=l)return M; if(a<=l&&r<=b)return A[k]; return min(q(a,b,2*k,l,(l+r)/2),q(a,b,2*k+1,(l+r)/2,r));} public: RMQ(vector<int>v){ n=1;while(n<(int)v.size())n*=2; A=vector<int>(2*n); for(int k=n;k>0;k/=2) for(int i=0;i<k;i++) A[k+i]=k==n?i<(int)v.size()?v[i]:0:min(A[2*(k+i)],A[2*(k+i)+1]);} int query(int l,int r){ return q(l,r,1,0,n);} }; int main() { int n,m; cin>>n>>m; string s; cin>>s; // 長さiの部分文字列の開始位置 vector<vector<int> > T(n+1); int l, r; l = r = 0; for ( int i=0; i<m; i++ ) { string q; cin>>q; if ( q=="L++") l++; if ( q=="L--") l--; if ( q=="R++") r++; if ( q=="R--") r--; T[r-l+1].push_back(l); } // 接尾辞配列、LCPのRMQ、逆接尾辞配列 vector<int> SA = SuffixArray(s); RMQ Q(LCP(s,SA)); vector<int> R(n); for ( int i=0; i<n; i++ ) R[SA[i]] = i; int ans = 0; for ( int w=1; w<=n; w++ ) { vector<int> A; for ( int i=0; i<(int)T[w].size(); i++ ) A.push_back(R[T[w][i]]); sort(A.begin(),A.end()); for ( int i=0; i<(int)T[w].size(); i++ ) if ( i==0 || A[i-1]!=A[i] && Q.query(A[i-1],A[i])<w ) ans++; } cout << ans << endl; return 0; }