后缀数组 hash求LCP BZOJ 4310: 跳蚤

后缀数组的题博客里没放进去过。。所以挖了一题写写 充实下博客 顺便留作板子。。

一个字符串S中 内容不同的子串 有 sigma{n-sa[i]+1-h[i]}   （噢 这里的h[]就是大家熟知的height[]）

所以l=1,r=上述sigma 二分 答案是字典序第几大的子串。

然后 求S中第k大的子串W ： 因为h[i]是与i-1有关的 所以要从n downto 1，k-=n-sa[i]+1-h[i] 至 k再减就非正了

显然这样扫过来 子串字典序是递减的  因此可以得到第k大子串W

然后再贪心 n downto 1 若遇到比 W大的子串 就划分，验证 当前二分的这个第k大可不可行

判断 比W大还是小 用hash 二分求LCP即可

 #include <bits/stdc++.h>

 #define N 200005

 #define LL long long

 using namespace std;

 const LL mo=;

 int F[],a[N],rank[N],sa[N],h[N],g1[N],g2[N],next[N],n,m,ans,k,t,l,r,mid,x,y,z;

 char S[N]; LL f[N],w[N];

 int oh(int k,int t,int p,int q){

     int l=,r=min(t-k,q-p)+,j;

     while (l<r){

         j=l+r+>>;

         (f[k+j-]-f[k-]*w[j]%mo+mo)%mo==(f[p+j-]-f[p-]*w[j]%mo+mo)%mo?

         l=j:r=j-;

     }

     if (k+l>t) return ;

     if (p+l>q) return ;

     return a[k+l]>a[p+l];

 }

 int jud(int u){

     int p,q,k,t;

     for (int i=n;i;--i)

         if (n-sa[i]+-h[i]<u) u-=n-sa[i]+-h[i];

         else {p=sa[i];q=n-u+;break;}

     t=n; k=;

     for (int i=n;i;)

     if (oh(i,t,p,q)){

         if (i==t) return ;

         t=i; ++k;

     } else --i;

     if (k>m) return ; return ;

 }

 int main(){

     scanf("%d",&m); scanf("%s",S+); n=strlen(S+);

     w[]=;

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

         a[i]=S[i]-'a'+;

         F[a[i]]=;

         f[i]=(f[i-]*+a[i])%mo;

         w[i]=w[i-]*%mo;

     }

     for (int i=;i<=;++i) F[i]+=F[i-];

     for (int i=;i<=n;++i) rank[i]=F[a[i]]; t=F[];

     for (int m=;m<n;m<<=){

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

             next[i]=g1[rank[i+m]];

             g1[rank[i+m]]=i;

         }

         for (int i=t;i>=;--i){

             for (int j=g1[i];j;j=k){

                 k=next[j]; next[j]=g2[rank[j]]; g2[rank[j]]=j;

             }

             g1[i]=;

         }

         z=;

         for (int i=;i<=t;++i){

             y=-;

             for (int j=g2[i];j;j=k){

                 k=next[j]; next[j]=;

                 if (y!=rank[j+m]) y=rank[j+m],++z;

                 h[j]=z;

             }

             g2[i]=;

         }

         t=z;

         for (int i=;i<=n;++i) rank[i]=h[i];

     }

     for (int i=;i<=n;++i) sa[rank[i]]=i,h[i]=;

     for (int i=,k=;i<=n;++i)

     if (rank[i]!=){

         if (k) --k;

         while (a[i+k]==a[sa[rank[i]-]+k]) ++k;

         h[rank[i]]=k; r+=n-i+-k;

     }

     l=; ++r;

     while (l<r){

         k=l+r+>>;

         jud(k)?l=k:r=k-;

     }

     for (int i=n;i;--i)

     if (n-sa[i]+-h[i]<l) l-=n-sa[i]+-h[i];

     else {k=sa[i];t=n-l+;break;}

     for (int i=k;i<=t;++i) printf("%c",a[i]+'a'-);

     return ;

 }

Assassin