POJ 3261 后缀数组的应用

题目：

题意：

    给出一个串，求这个串的最长的出现过至少k次的子串。出现的位置可以重叠。

代码如下：（这里采用了edward_mj的代码）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=22222;
struct gtp{int data[3],next;}g[N];
int n,q,s[N],sa[N],rank[N],a[N][3],e,ls[N],height[N],G[N];

inline void add(int x,int data[]){
       e++;
       g[e].next=ls[x]; ls[x]=e;
       memcpy(g[e].data,data,sizeof(a[0]));
}

void Jsort(){
     for (int k=1;k>=0;k--){
         e=0;
         memset(ls,0,sizeof(int)*(n+1));
         for (int i=n;i>=1;i--) add(a[i][k],a[i]);
         int tail=0;
         for (int i=0;i<=n;i++)
           for (int t=ls[i];t!=0;t=g[t].next)
             memcpy(a[++tail],g[t].data,sizeof(a[0]));
     }
}

void Sort(int l,int r){
     if (l>=r) return;
     int i=l,j=r,mid=s[sa[l+r>>1]];
     while (i<j){
           while (s[sa[i]]<mid) i++;
           while (s[sa[j]]>mid) j--;
           if (i<=j){
             swap(sa[i],sa[j]);
             i++; j--;
           }
     }
     Sort(l,j);
     Sort(i,r);
}

void build(){
     for (int i=1;i<=n;i++) sa[i]=i;
     Sort(1,n);
     int tail=0;
     for (int i=1;i<=n;i++){
         if (i==1 || s[sa[i]]!=s[sa[i-1]]) tail++;
         rank[sa[i]]=tail;
     }
     for (int k=1;1<<k-1<n;k++){
         for (int i=1;i<=n;i++){
             a[i][0]=rank[i];
             if (i+(1<<k-1)<=n) a[i][1]=rank[i+(1<<k-1)];
                           else a[i][1]=0;
             a[i][2]=i;
         }
         Jsort();
         tail=0;
         for (int i=1;i<=n;i++){
             if (i==1 || a[i][0]!=a[i-1][0] || a[i][1]!=a[i-1][1]) tail++;
             rank[a[i][2]]=tail;
         }
     }
     for (int i=1;i<=n;i++) sa[rank[i]]=i;
}

void make_height(){
     memset(height,0,sizeof(int)*(n+1));
     for (int i=1;i<=n;i++){
         if (rank[i]==1) continue;
         int st=max(0,height[rank[i-1]]-1),j=i+st,k=sa[rank[i]-1]+st;
         while (j<=n && k<=n && s[j]==s[k]) {st++;j++;k++;}
         height[rank[i]]=st;
     }
}

bool flag(int limit){
     int Gn=1; G[1]=1;
     for (int i=2;i<=n;i++)
       if (height[i]>=limit) G[i]=Gn;
                        else G[i]=++Gn;
     int j=1;
     for (int i=1;i<=Gn;i++){
         int st=j;
         while (j<=n && G[j]==i) j++;
         if (j-st>=q) return true;
     }
     return false;
}

int binary(){
     int l=0,r=n,mid;
     while (l+1<r){
           mid=l+r>>1;
           if (flag(mid)) l=mid;
                     else r=mid-1;
     }
     if (flag(r)) return r;
     return l;
}

int main(){
    scanf("%d%d",&n,&q);
    for (int i=1;i<=n;i++) scanf("%d",&s[i]);
    build();
    make_height();
    int ans=binary();
    printf("%d\n",ans);
}