hdu6704 2019CCPC网络选拔赛1003 K-th occurrence 后缀数组

题意：给你一个长度为n的字符串,有q个询问，每次询问一个子串s(l,r）第k次出现的位置，若子串出现次数少于k次输出-1.

解题思路：先把SA跑出来，然后对于每次询问可以由l和rank[]找到l在所有后缀中的排名，再用两次二分求出使得LCP(L,R)包含s(l,r)的最大区间[L,R]，LCP可以借助height[]的性质和ST表求得，即[L,R]包含rank[l]且min{height[L+1],height[L+2],...,height[R]}>=r-l+1。现在问题就转化为了求[L,R]中第k大的sa[i]，这个就是主席树经典操作了。

感觉这个做法挺容易想出来的，但是就是写起来有些麻烦，对SA不熟悉的话就容易写劈叉。

听机房大佬说还有后缀自动机+线段树合并的写法：传送门

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=2e5+5;

const int INF=0x3f3f3f3f;

char s[maxn];

int height[maxn],c[maxn],x[maxn],y[maxn],sa[maxn],rk[maxn];

void SA(int n){

    n++;

    int i,j,k,m=128;

    for(i=0;i<m;i++) c[i]=0;

    for(i=0;i<n;i++)c[x[i]=s[i]]++;

    for(i=1;i<m;i++) c[i]+=c[i-1];

    for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;

    for(j=1;j<=n;j<<=1){

      k=0;

      for(i=n-j;i<n;i++) y[k++]=i;

      for(i=0;i<n;i++) if(sa[i]>=j) y[k++]=sa[i]-j;

      for(i=0;i<m;i++) c[i]=0;

      for(i=0;i<n;i++) c[x[y[i]]]++;

      for(i=1;i<m;i++) c[i]+=c[i-1];

      for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];

      swap(x,y);

      m=0;

      x[sa[0]]=m++;

      for(i=1;i<n;i++){

          if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]) x[sa[i]]=m-1;

          else x[sa[i]]=m++;

      }

      if(m>=n) break;

    }

    k=0;

    for(i=0;i<n;i++) rk[sa[i]]=i;

    for(i=0;i<n-1;i++){

      if(k) k--;

      j=sa[rk[i]-1];

      while(s[i+k]==s[j+k]) k++;

      height[rk[i]]=k;

    }

//    cout<<"sa:";for(int i=0;i<n;i++)cout<<sa[i]<<" ";cout<<endl;

//    cout<<"rk:";for(int i=0;i<n;i++)cout<<rk[i]<<" ";cout<<endl;

//    cout<<"h:";for(int i=1;i<n-1;i++)cout<<height[i]<<" ";cout<<endl;

//

//    for(int i=0;i<n;i++){

//        for(int j=sa[i];j<n;j++)putchar(s[j]);

//        putchar('\n');

//    }

}

int n,m;

int mi[maxn][20],lg[maxn];

void initRMQ()

{

    memset(mi,0x3f,sizeof(mi));

    lg[1]=0;

    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;

    for(int i=1;i<=n;i++)mi[i][0]=height[i];

    for(int j=1;j<=lg[n];j++)

        for(int i=1;i<=n;i++)

            mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);

}

int queryRMQ(int x,int y)

{

    int l=min(x,y)+1,r=max(x,y);

    int d=lg[r-l+1];

    //cout<<"llrr:"<<l<<" "<<r<<" "<<min(mi[l][d],mi[r-(1<<d)+1][d])<<endl;

    return min(mi[l][d],mi[r-(1<<d)+1][d]);;

}

int T[maxn],cnt;

int sum[maxn<<5],L[maxn<<5],R[maxn<<5];

inline int build(int l,int r)

{

    int rt=++cnt;

    sum[rt]=0;

    int mid=(l+r)/2;

    if(l<r){

        L[rt]=build(l,mid);

        R[rt]=build(mid+1,r);

    }

    return rt;

}

inline int update(int pre,int l,int r,int x)

{

    int rt=++cnt;

    L[rt]=L[pre];

    R[rt]=R[pre];

    sum[rt]=sum[pre]+1;

    int mid=(l+r)/2;

    if(l<r){

        if(x<=mid)L[rt]=update(L[pre],l,mid,x);

        else R[rt]=update(R[pre],mid+1,r,x);

    }

    return rt;

}

inline int query(int u,int v,int l,int r,int k)

{

    if(l>=r)return l;

    int mid=(l+r)/2;

    int x=sum[L[v]]-sum[L[u]];

    if(x>=k)return query(L[u],L[v],l,mid,k);

    else return query(R[u],R[v],mid+1,r,k-x);

}

int solve(int l,int r,int k)

{

    int len=r-l+1;

    int lp=rk[l],rp=rk[l];

    int ll=0,rr=rk[l],mid;

    int mii;

    while(ll<=rr){

        mid=(ll+rr)/2;

        mii=queryRMQ(mid,rk[l]);

        if(mii>=len)lp=mid,rr=mid-1;

        else ll=mid+1;

    }

    ll=rk[l]+1,rr=n;

    while(ll<=rr){

        mid=(ll+rr)/2;

        mii=queryRMQ(rk[l],mid);

        if(mii>=len)rp=mid,ll=mid+1;

        else rr=mid-1;

    }

//    cout<<"lr:"<<rk[l]<<" "<<lp<<" "<<rp<<endl;

    if(rp-lp+1<k)return -1;

    return query(T[lp-1],T[rp],0,n-1,k)+1;

}

int main()

{

//#ifndef ONLINE_JUDGE

//    freopen("in.txt","r",stdin);

//#endif

    int Case;

    scanf("%d",&Case);

    while(Case--){

        scanf("%d %d",&n,&m);

        scanf("%s",s);

        SA(n);

        initRMQ();

        cnt=0;

        T[0]=build(0,n-1);

        for(int i=1;i<=n;i++)T[i]=update(T[i-1],0,n-1,sa[i]);

        int l,r,k;

        while(m--){

            scanf("%d %d %d",&l,&r,&k);

            printf("%d\n",solve(l-1,r-1,k));

        }

    }

    return 0;

}

巴特西

hdu6704 2019CCPC网络选拔赛1003 K-th occurrence 后缀数组

最新文章

热门文章