题目大意：
在原串中找到一个拥有连续相同子串最多的那个子串
比如dababababc中的abababab有4个连续的ab，是最多的
如果有同样多的输出字典序最小的那个
这里用后缀数组解决问题：
枚举连续子串的长度l ， 那么从当前位置0出发每次递增l，拿 i 和 i+l 开头的后缀求一个前缀和val ， 求解依靠RMQ 得到区间 rank(i),rank(i+l)
那么连续的子串个数应该是val/l+1
但是由于你不一定是从最正确的位置出发，那么我们就需要不断将这个i往前推l位，直到某一位字符不匹配，推移的过程中，可能与形成连续串多出的
部分形成一个新的子串，那么个数应该加1，且不断更新推移过程中的rank值，尽量取到rank值小的开头的字符串
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 #include <cmath> 5 #include <algorithm> 6 #include <iostream> 7 using namespace std; 8 typedef long long ll; 9 const int N = 100010; 10 int r[N] , sa[N] , _rank[N] , height[N]; 11 int wa[N] , wb[N] , wv[N] , wsf[N]; 12 int cmp(int *r , int a , int b , int l){return r[a]==r[b]&&r[a+l]==r[b+l];} 13 void da(int *r , int *sa , int n , int m) 14 { 15 int i,j,p,*x=wa,*y=wb,*t; 16 for(i=0;i<m;i++)wsf[i]=0; 17 for(i=0;i<n;i++)wsf[x[i]=r[i]]++; 18 for(i=1 ; i<m ; i++) wsf[i]+=wsf[i-1]; 19 for(i=n-1;i>=0;i--) sa[--wsf[x[i]]]=i; 20 for(j=1,p=1;p<n;j*=2,m=p){ 21 for(p=0,i=n-j;i<n;i++) y[p++]=i; 22 for(i=0;i<n;i++) if(sa[i]>=j)y[p++]=sa[i]-j; 23 for(i=0;i<n;i++) wv[i]=x[y[i]]; 24 for(i=0;i<m;i++) wsf[i]=0; 25 for(i=0;i<n;i++) wsf[wv[i]]++; 26 for(i=1;i<m;i++) wsf[i]+=wsf[i-1]; 27 for(i=n-1;i>=0;i--) sa[--wsf[wv[i]]]=y[i]; 28 for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++) 29 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 30 } 31 return; 32 } 33 void callHeight(int *r , int *sa , int n) 34 { 35 int i,j,k=0; 36 for(i=1;i<=n;i++) _rank[sa[i]]=i; 37 for(i=0;i<n;height[_rank[i++]]=k) 38 for(k?k--:0,j=sa[_rank[i]-1];r[i+k]==r[j+k];k++); 39 return; 40 } 41 42 int dp[N<<1][18] , n; 43 char s[N]; 44 void ST() 45 { 46 memset(dp , 0x3f , sizeof(dp)); 47 for(int i=1 ; i<=n ; i++)dp[i][0]=height[i]; 48 for(int k=1 ; (1<<k)<=n ; k++){ 49 for(int i=1 ; i<=n ; i++){ 50 dp[i][k] = min(dp[i][k-1] , dp[i+(1<<(k-1))][k-1]); 51 } 52 } 53 } 54 int RMQ(int s , int t) 55 { 56 int d = t-s+1; 57 int k = (int)log2(d*1.0); 58 // cout<<s<<" "<<t<<" "<<k<<" "<<t-(1<<k)+1<<endl; 59 return min(dp[s][k] , dp[t-(1<<k)+1][k]); 60 } 61 int RMQPOS(int x , int y) 62 { 63 // cout<<"cal pos: "<<x<<" "<<y<<" "; 64 x = _rank[x] , y = _rank[y]; 65 if(x>y){int t=x;x=y,y=t;} 66 // cout<<x<<" "<<y<<" "<<RMQ(x+1,y)<<" "; 67 return RMQ(x+1,y); 68 } 69 void solve(int &mxTime , int &ansl , int &ansLf) 70 { 71 ansl = ansLf = mxTime = 0; 72 for(int l=1 ; l<=n/2 ; l++) {//最外层循环节长度 73 for(int i=0 ; i+l<n ; i+=l){ 74 int mxl = RMQPOS(i , i+l); 75 int time = mxl/l+1; 76 77 int del = time*l-mxl , curpos=i , mxRank=_rank[i]; 78 int t; 79 for(t=1 ; t<l ; t++){ 80 if(i<t || s[i-t]!=s[i+l-t]) break; 81 if(_rank[i-t]<mxRank){ 82 mxRank = _rank[i-t]; 83 curpos = i-t; 84 } 85 if(t==del){ 86 mxRank = _rank[i-t]; 87 curpos = i-t , time++; 88 } 89 } 90 91 if(mxTime<time||(mxTime==time&&mxRank<_rank[ansLf])) mxTime=time,ansl=time*l,ansLf=curpos; 92 93 } 94 } 95 } 96 int main() 97 { 98 //freopen("a.in" , "r" , stdin); 99 int cas =0 ; 100 while(scanf("%s" , s)) 101 { 102 n = strlen(s); 103 if(n==1 && s[0]=='#') break; 104 printf("Case %d: ",++cas); 105 for(int i=0 ; i<n ; i++) r[i] = s[i]-'a'+1; 106 r[n]=0; 107 da(r,sa,n+1,27); 108 callHeight(r,sa,n); 109 ST(); 110 111 int mxTime , ansl , ansLf; 112 solve(mxTime , ansl , ansLf); 113 if(mxTime==1){ 114 char minc='a'; 115 for(int i=0 ; i<n ; i++){ 116 minc=min(minc , s[i]); 117 } 118 printf("%c\n" , minc); 119 continue; 120 } 121 for(int i=0 , j=ansLf ; i<ansl ; i++,j++) printf("%c" , s[j]); 122 puts(""); 123 } 124 return 0; 125 }