POJ 3294 后缀数组 分组思想

题意：

找出最长的串，使其是在给定的N个串中，超过N/2个得子串。

如果有多个最长的串，那么按字典序输出所有的串。

分析：

先把所有串串起来，期间用不同的特殊字符间隔。

这里是为了保证后缀数组不会隔着组弄成lcp。

这题可以先用后缀数组处理出height数组。

然后二分答案（长度）。

Next，按顺序将height分组（每组是连续的），使得每一组里除了第一以外的height值都>=limit

如果里面有一组包含超过N/2个所归属的串，那么flag=true

如果flag=true，那么放大答案，否则减小。

最后按顺序取来输出就行了。

插曲：

1A

这次后缀数组部分短了大概50行= =，但还是比较长。

code：

#include #include #include using namespace std;
const int N=200000;
struct gtp{int x,data[3],next;}g[N];
char s[N],ts[N];
int n,sa[N],rank[N],height[N],len,v[N],a[N][3],ls[N],e,G[N];
int mark[N];

void init(){
    memset(s,0,sizeof(s));
    memset(v,0,sizeof(v));
    memset(sa,0,sizeof(sa));
    memset(rank,0,sizeof(rank));
    memset(height,0,sizeof(height));
    len=0;
    char tmp=’A’;
    for (int i=1;i<=n;i++){
        scanf("%s",&ts);
        int tlen=strlen(ts);
        for (int j=0;j          s[++len]=ts[j];
          v[len]=i;
        }
        s[++len]=tmp;
        tmp++;
        if (tmp>’Z’) tmp=’A’;
    }
}

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

inline void add(int x,int data[]){
    e++;
    g[e].x=x; 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)*(len+1));
        for (int i=len;i>=1;i–) add(a[i][k],a[i]);
        int tail=0;
        for (int i=0;i<=len;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<=len;i++) sa[i]=i;
    Sort(1,len);
    int tail=0;
    for (int i=1;i<=len;i++){
        if (i==1 || s[sa[i]]!=s[sa[i-1]]) tail++;
        rank[sa[i]]=tail;
    }
    for (int k=2;k<=len;k<<=1){
        for (int i=1;i<=len;i++){
            a[i][0]=rank[i];
            if (i+(k>>1)<=len) a[i][1]=rank[i+(k>>1)];
                          else a[i][1]=0;
            a[i][2]=i;
        }
        Jsort();
        tail=0;
        for (int i=1;i<=len;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<=len;i++) sa[rank[i]]=i;
}

void GetHeight(){
    for (int i=1;i<=len;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<=len && k<=len && s[j]==s[k]){st++; j++; k++;}
        height[rank[i]]=st;
    }
}

bool flag(int limit){
    bool ret=false;
    int Gn=1; G[1]=1;
    for (int i=2;i<=len;i++)
      if (height[i]>=limit) G[i]=Gn;
                       else G[i]=++Gn;
    memset(mark,0,sizeof(int)*(len+1));
    int j=1,num;
    for (int i=1;i<=Gn;i++){
        num=0;
        while (j<=len && G[j]==i) {
            if (v[sa[j]]!=0 && mark[v[sa[j]]]!=i){
                mark[v[sa[j]]]=i;
                num++;
            }
            j++;
        }
        if (num>n/2) ret=true;
    }
    return ret;
}

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

void print(int ans){
    if (ans==0) printf("?n");
    else{
        int Gn=1; G[1]=1;
        for (int i=2;i<=len;i++)
          if (height[i]>=ans) G[i]=Gn;
                         else G[i]=++Gn;
        memset(mark,0,sizeof(int)*(len+1));
        int j=1,num,st;
        for (int i=1;i<=Gn;i++){
          num=0;
          st=j;
          while (j<=len && G[j]==i) {
              if (v[sa[j]]!=0 && mark[v[sa[j]]]!=i){
                  mark[v[sa[j]]]=i;
                  num++;
              }
              j++;
          }
          if (num>n/2){
              for (int k=0;k                printf("%c",s[sa[st]+k]);
              printf("n");
          }
        }
    }
}

int main(){
    scanf("%dn",&n);
    while (n!=0){
        init();
        buildarr();
        GetHeight();
        int ans=binary();
        print(ans);
        scanf("%dn",&n);
        if (n!=0) printf("n");
    }
    return 0;
}