【POJ11855】 Buzzwords （后缀数组）

【题意】

　　给定一个文本，求出长度为1， 2， 3， 4， 5....的字符串最大出现次数，一直找到出现次数不大于1为止。

【分析】

　　直接for两遍。按枚举的长度分组，求出小组成员个数的max即可。

代码如下：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define Maxl 100010

 #define INF 0xfffffff

 int l,len;

 char s[Maxl];

 int c[Maxl],cl;

 int mymin(int x,int y) {return x<y?x:y;}

 int mymax(int x,int y) {return x>y?x:y;}

 void init()

 {

     len=strlen(s);

     cl=;

     for(int i=;i<len;i++) if(s[i]!=' ')

       c[++cl]=s[i]-'A'+;

 }

 int sa[Maxl],rk[Maxl],y[Maxl],wr[Maxl],Rs[Maxl];

 void get_sa(int m)

 {

     memcpy(rk,c,sizeof(rk));

     for(int i=;i<=m;i++) Rs[i]=;

     for(int i=;i<=cl;i++) Rs[rk[i]]++;

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

     for(int i=cl;i>=;i--) sa[Rs[rk[i]]--]=i;

     int ln=,p=;

     while(p<cl)

     {

         int k=;

         for(int i=cl-ln+;i<=cl;i++) y[++k]=i;

         for(int i=;i<=cl;i++) if(sa[i]>ln) y[++k]=sa[i]-ln;

         for(int i=;i<=cl;i++) wr[i]=rk[y[i]];

         for(int i=;i<=m;i++) Rs[i]=;

         for(int i=;i<=cl;i++) Rs[wr[i]]++;

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

         for(int i=cl;i>=;i--) sa[Rs[wr[i]]--]=y[i];

         for(int i=;i<=cl;i++) wr[i]=rk[i];

         for(int i=cl+;i<=cl+ln;i++) wr[i]=;

         p=,rk[sa[]]=;

         for(int i=;i<=cl;i++)

         {

             if(wr[sa[i]]!=wr[sa[i-]]||wr[sa[i]+ln]!=wr[sa[i-]+ln]) p++;

             rk[sa[i]]=p;

         }

         ln*=,m=p;

     }

     sa[]=rk[]=;

 }

 int height[Maxl];

 void get_he()

 {

     int k=;

     for(int i=;i<=cl;i++) if(rk[i]!=)

     {

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

         if(k) k--;

         while(c[i+k]==c[j+k]&&i+k<=cl&&j+k<=cl) k++;

         height[rk[i]]=k;

     }

 }

 void ffind()

 {

     for(int i=;i<=cl;i++)//枚举长度i

     {

         int cnt=,ans=;

         for(int j=;j<=cl;j++)

         {

             cnt++;

             if(height[j+]<i||j==cl)//是一组的结束

             {

                 if(cnt!=) ans=mymax(ans,cnt);

                 cnt=;

             }

         }

         if(ans<=) break;

         printf("%d\n",ans);

     }

 }

 int main()

 {

     bool ok=;

     while(gets(s))

     {

         if(ok) printf("\n");

         ok=;

         init();

         get_sa();

         get_he();

         ffind();

     }

     return ;

 }

[UVA11855]

2016-07-19 16:31:07