Maximum repetition substring (poj3693 后缀数组求重复次数最多的连续重复子串）

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <math.h>
  4 #include <vector>
  5 #include <string.h>
  6 using namespace std;
  7 #define N 100005
  8 char a[N];
  9 int c[N],d[N],e[N],sa[N],height[N],n,b[N],m,dp[N][21];
 10 int cmp(int *r,int a,int b,int l)
 11 {
 12     return r[a]==r[b]&&r[a+l]==r[b+l];
 13 }
 14 void da()
 15 {
 16     int i,j,p,*x=c,*y=d,*t;
 17     memset(b,0,sizeof(b));
 18     for(i=0; i<n; i++)b[x[i]=a[i]]++;
 19     for(i=1; i<m; i++)b[i]+=b[i-1];
 20     for(i=n-1; i>=0; i--)sa[--b[x[i]]]=i;
 21     for(j=1,p=1; p<n; j*=2,m=p)
 22     {
 23         for(p=0,i=n-j; i<n; i++)y[p++]=i;
 24         for(i=0; i<n; i++)if(sa[i]>=j)y[p++]=sa[i]-j;
 25         for(i=0; i<n; i++)e[i]=x[y[i]];
 26         for(i=0; i<m; i++)b[i]=0;
 27         for(i=0; i<n; i++)b[e[i]]++;
 28         for(i=1; i<m; i++)b[i]+=b[i-1];
 29         for(i=n-1; i>=0; i--)sa[--b[e[i]]]=y[i];
 30         for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)
 31             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
 32     }
 33 }
 34 void callheight()
 35 {
 36     int i,j,k=0;
 37     b[0]=0;
 38     for(i=1; i<n; i++)b[sa[i]]=i;
 39     for(i=0; i<n-1; height[b[i++]]=k)
 40         for(k?k--:0,j=sa[b[i]-1]; a[i+k]==a[j+k]; k++);
 41 }
 42 int fun(int i,int j)
 43 {
 44     i=b[i];
 45     j=b[j];
 46     if(i>j)swap(i,j);
 47     i++;
 48     int k=(int)(log(j-i+1.0)/log (2.0));
 49     return min(dp[i][k],dp[j-(1<<k)+1][k]);
 50 }
 51 void initrmq()
 52 {
 53     int i,j;
 54     memset(dp,0,sizeof(dp));
 55     for(i=0; i<=n; i++)
 56         dp[i][0]=height[i];
 57     for(j=1; (1<<j)<=n; j++)
 58         for(i=0; i+(1<<j)<=n; i++)
 59             dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
 60 }
 61 int main()
 62 {
 63     int t=1,i,j,yy;
 64     while(~scanf("%s",a))
 65     {
 66         yy=0;
 67         if(a[0]==‘#‘)break;
 68         n=strlen(a);
 69         n++;
 70         m=130;
 71         da();
 72         callheight();
 73         initrmq();
 74         memset(c,0,sizeof(c));
 75         int max=1;
 76         n--;
 77         for(i=1; i<n/2; i++)
 78         {
 79             for(j=0; j+i<n; j+=i)
 80             {
 81                 int k=fun(j,j+i);
 82                 int kk=k/i+1;
 83                 int tt=i-k%i;
 84                 tt=j-tt;
 85                 if (tt>=0&&k%i!=0)
 86                     if(fun(tt,tt+i)>=k)
 87                         kk++;
 88                 if(max<kk)
 89                 {
 90                     yy=0;
 91                     c[yy++]=i;
 92                     max=kk;
 93                 }
 94                 else if(max==kk)
 95                 {
 96                     c[yy++]=i;
 97                 }
 98             }
 99         }
100         printf("Case %d: ",t++);
101         int sta,m;
102         for(i=1; i<n; i++)
103         {
104             for(j=0; j<yy; j++)
105             {
106 
107                 if(fun(sa[i],sa[i]+c[j])>=(max-1)*c[j])
108                 {
109                     sta=sa[i];
110                     m=max*c[j];
111                     break;
112                 }
113             }
114             if(j<yy)break;
115         }
116         for(i=0; i<m; i++)putchar(a[sta+i]);
117         printf("\n");
118     }
119 }