HDU 2459 Maximum repetition substring

题目：Maximum repetition substring

链接：http://acm.hdu.edu.cn/showproblem.php?pid=2459

题意：给你一个字符串，求连续重复出现次数最多的子串（不重叠），如果有多个，输出字典序最小的那个。别如aacdabcdab，a连续着重复出现2次，cdab连续着出现2次，但aa的字典序小，所以输出aa。

思路：

　　枚举+后缀树组+rmq

　　枚举重复串的长度，后缀数组预处理出height数组，rmq预处理height，实现O（1）查询。

　　给几组测试数据：

　　1. aabababa，答案为ababab，不是bababa

　　2. atbctbctb，答案是bctbct，不是ctbctb

　　3. aabcabcabcab，答案是abcabcabc，不是cabcabcab

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<math.h>
  4 #define N 200020
  5 char s1[200020];
  6 int ws[N],wv[N];
  7 int sa[N],r[N],wx[N],wy[N];
  8 int height[N];
  9 bool cmp(int *r,int a,int b,int l)
 10 {
 11   return r[a]==r[b]&&r[a+l]==r[b+l];
 12 }
 13 void da(int *r,int n,int m)
 14 {
 15   //注意，这里的n必须比原始数组大小大1
 16   int *x=wx,*y=wy;
 17   for(int i=0;i<m;i++) ws[i]=0;
 18   for(int i=0;i<n;i++) ws[x[i]=r[i]]++;
 19   for(int i=1;i<m;i++) ws[i]+=ws[i-1];
 20   for(int i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
 21   //这里的x[i] 表示下标i的第一关键字排名
 22   int i,j,p,*t;
 23   for(j=1,p=1;p<n;j*=2,m=p)
 24   {
 25     for(p=0,i=n-j;i<n;i++) y[p++]=i;
 26     for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
 27     //此时的y[i] 表示第二关键字排第i的下标是y[i]
 28     for(i=0;i<n;i++) wv[i]=x[y[i]];
 29     for(i=0;i<m;i++) ws[i]=0;
 30     for(i=0;i<n;i++) ws[wv[i]]++;
 31     for(i=1;i<m;i++) ws[i]+=ws[i-1];
 32     for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
 33     for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
 34       x[sa[i]]=cmp(y,sa[i],sa[i-1],j)?p-1:p++;
 35   }
 36   for(int i=0;i<n;i++)
 37   {
 38     r[sa[i]]=i;
 39   }
 40 }
 41 void calHeight(int n)
 42 {
 43   int h=0;
 44   for(int i=0;i<n;i++)
 45   {
 46     if(r[i]==0) h=0;
 47     else
 48     {
 49       int k=sa[r[i]-1];
 50       if(--h<0) h=0;
 51       while(s1[k+h]==s1[i+h]) h++;
 52     }
 53     height[r[i]]=h;
 54   }
 55 }
 56 int f[100010][17];
 57 int min(int x,int y)
 58 {
 59   return x<y?x:y;
 60 }
 61 int max(int x,int y)
 62 {
 63   return x<y?y:x;
 64 }
 65 void rmq(int n)
 66 {
 67   for(int j=0;j<n;j++) f[j][0]=height[j];
 68   for(int i=1;i<20;i++)
 69   {
 70     for(int j=0;j<n;j++)
 71     {
 72       if(j+(1<<i)-1 < n)
 73       {
 74         f[j][i]=min(f[j][i-1],f[j+(1<<i-1)][i-1]);
 75       }
 76     }
 77   }
 78 }
 79 int look(int x,int y)
 80 {
 81   x=r[x];
 82   y=r[y];
 83   if(x>y) x^=y^=x^=y;
 84   x++;
 85   int k=(int)log2((double)(y-x+1));
 86   return min(f[x][k],f[y-(1<<k)+1][k]);
 87 }
 88 
 89 bool cmp(int sl,int l)
 90 {
 91   if(r[sl]>r[l]) return 1;
 92   return 0;
 93 }
 94 
 95 void solve(int n)
 96 {
 97   int maxt=0,sl=0,sr=0;
 98   for(int i=1;i<=n/2;i++)
 99   {
100     for(int j=0;j+i<n;j+=i)
101     {
102       int l=j;
103       int r=j+i;
104       int lcp=look(l,r);
105       int d=lcp/i+1;
106       int t=j-(i-lcp%i);
107       for(int k=l-1;k>=0&&k+i>j&&s1[k]==s1[k+i];k--)
108       {
109         if(k==t)
110         {
111           d++;
112           l=k;
113         }
114         else if(cmp(l,k))
115         {
116           l=k;
117         }
118       }
119       if(d>maxt)
120       {
121         sl=l;
122         sr=l+d*i-1;
123         maxt=d;
124       }
125       else if(d==maxt&&cmp(sl,l))
126       {
127         sl=l;
128         sr=l+d*i-1;
129       }
130     }
131   }
132   for(int i=sl;i<=sr;i++)
133   {
134     printf("%c",s1[i]);
135   }
136   printf("
");
137 }
138 
139 int main()
140 {
141   int cas=1;
142   while(scanf("%s",s1)!=EOF)
143   {
144     if(s1[0]=='#') break;
145     int len=strlen(s1);
146     for(int i=0;i<len;i++)
147       r[i]=s1[i]-'a'+1;
148     r[len++]=0;
149     da(r,len,27);
150     calHeight(len);
151     rmq(len);
152     printf("Case %d: ",cas++);
153     solve(len-1);
154 
155 
156   }
157   return 0;
158 }