JAGSummerCamp12Day3B E : Substring

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;
}