SPOJ 220 后缀数组 分组思想

题意：

题目：https://www.spoj.pl/problems/PHRASES/

给定N个字符串，让你求一个最长的串，使得他满足：

在每个串中它都出现过>=两次，而且出现的位置不重叠。

分析：

就是构造后缀数组，然后二分答案，用分组思想，看能否实现。

HINT

一开始没看到不能重叠，WA了一遍。

code：

#include #include #include using namespace std;
const int N=111111;
char s[N];
struct gtp{int data[3],next;}g[N];
int cn,ls[N],color[N],e,n,sa[N],rank[N],a[N][3],G[N],hash[N],num[N],height[N],maxsa[N],minsa[N],list[N];

void init(){
     char inschar=’A’,ch;
     scanf("%dn",&cn);
     n=0;
     for (int i=1;i<=cn;i++){
         while (scanf("%c",&ch)!=EOF && ch!=’n’)
           if (ch>=’a’ && ch<='z'){
             s[++n]=ch;
             color[n]=i;
           }
         s[++n]=inschar++;
         color[n]=0;
     }
}

inline bool cmp(int x,int y){
     if (s[x]     return false;
}

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 buildarr(){
     for (int i=1;i<=n;i++) sa[i]=i;
     sort(&sa[1],&sa[n+1],cmp);
     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<         int t=1<         for (int i=1;i<=n;i++){
             a[i][0]=rank[i];
             if (i+t<=n) a[i][1]=rank[i+t];
                    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 MakeHeight(){
     memset(height,0,sizeof(int)*(n+1));
     for (int i=1;i<=n;i++){
         if (rank[i]==1) continue;
         int st=max(height[rank[i-1]]-1,0),j=i+st,k=sa[rank[i]-1]+st;
         while (j<=n && k<=n && s[j]==s[k]) {j++;k++;st++;}
         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,total=0,tail=0;
         while (j<=n && G[j]==i) j++;
         for (int k=st;k           if (hash[color[sa[k]]]!=i){
             hash[color[sa[k]]]=i;
             num[color[sa[k]]]=1;
             minsa[color[sa[k]]]=sa[k];
             maxsa[color[sa[k]]]=sa[k];
             list[++tail]=color[sa[k]];
           }
           else{
             num[color[sa[k]]]++;
             minsa[color[sa[k]]]=min(minsa[color[sa[k]]],sa[k]);
             maxsa[color[sa[k]]]=max(maxsa[color[sa[k]]],sa[k]);
             if (num[color[sa[k]]]==2 && color[sa[k]]!=0) total++;
           }
         if (total!=cn) continue;
         bool ff=true;
         for (int k=1;k<=tail;k++)
           if (maxsa[k]-minsa[k]         if (ff) return true;
     }
     return false;
}

void binary(){
     int l=0,r=n,mid;
     while (l+1           mid=l+r>>1;
           if (flag(mid)) l=mid;
                     else r=mid-1;
     }
     if (flag(r)) printf("%dn",r);
             else printf("%dn",l);
}

int main(){
    int testcase;
    scanf("%d",&testcase);
    for (int i=1;i<=testcase;i++){
        init();
        buildarr();
        MakeHeight();
        binary();
    }
}