题意：
n<=1e5
思路：
From http://hzwer.com/6152.html
往后匹配多远 r 用ST表求lcp即可。。。往前 l 就把串反过来再做一下。。
但是有可能求出来的最长串可以前移/后移几位
即开头可以在落在[i−l,i−l+(l+r)mod L]
区间内字典序最小的还要用ST表找rank区间最值
有空需要学习一下结构体写法 一模一样的东西写多次太累了
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 typedef long long ll; 13 typedef unsigned int uint; 14 typedef unsigned long long ull; 15 typedef pair<int,int> PII; 16 typedef vector<int> VI; 17 #define fi first 18 #define se second 19 #define MP make_pair 20 #define N 110000 21 #define MOD 1000000007 22 #define eps 1e-8 23 #define pi acos(-1) 24 #define oo 1000000000 25 26 char ch[N]; 27 int n,i,s[N],sa[N],wa[N],wb[N],wc[N],wd[N],height[N],rank[N], 28 ans,mx,ansl,ansr,f[4][N][20],g[3][N],save[N],Log[N],bin[N]; 29 30 31 int read() 32 { 33 int v=0,f=1; 34 char c=getchar(); 35 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 36 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 37 return v*f; 38 } 39 40 bool cmp(int *r,int a,int b,int l) 41 { 42 return r[a]==r[b]&&r[a+l]==r[b+l]; 43 } 44 45 void getsa(int *r,int *sa,int n,int m) 46 { 47 int *x=wa,*y=wb,j,p; 48 for(i=0;i<n;i++) wc[x[i]=r[i]]++; 49 for(i=1;i<m;i++) wc[i]+=wc[i-1]; 50 for(i=n-1;i>=0;i--) sa[--wc[x[i]]]=i; 51 for(j=1,p=1;p<n;j*=2,m=p) 52 { 53 p=0; 54 for(i=n-j;i<n;i++) y[p++]=i; 55 for(i=0;i<n;i++) 56 if(sa[i]>=j) y[p++]=sa[i]-j; 57 for(i=0;i<n;i++) wd[i]=x[y[i]]; 58 for(i=0;i<m;i++) wc[i]=0; 59 for(i=0;i<n;i++) wc[wd[i]]++; 60 for(i=1;i<m;i++) wc[i]+=wc[i-1]; 61 for(i=n-1;i>=0;i--) sa[--wc[wd[i]]]=y[i]; 62 swap(x,y); 63 p=1; x[sa[0]]=0; 64 for(i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 65 } 66 } 67 68 void getheight(int *r,int *sa,int n) 69 { 70 int i,j,k=0; 71 for(i=1;i<=n;i++) rank[sa[i]]=i; 72 for(i=0;i<n;height[rank[i++]]=k) 73 { 74 if(k) k--; 75 j=sa[rank[i]-1]; 76 while(r[i+k]==r[j+k]) k++; 77 } 78 } 79 80 void init() 81 { 82 memset(s,0,sizeof(s)); 83 memset(sa,0,sizeof(sa)); 84 memset(wa,0,sizeof(wa)); 85 memset(wb,0,sizeof(wb)); 86 memset(wc,0,sizeof(wc)); 87 memset(wd,0,sizeof(wd)); 88 memset(height,0,sizeof(height)); 89 memset(rank,0,sizeof(rank)); 90 } 91 92 int lcp(int p,int x,int y) 93 { 94 int t; 95 int L=g[p][x]; 96 int R=g[p][y]; 97 if(L>R){t=L; L=R; R=t;} 98 L++; 99 int q=Log[R-L+1]; 100 return min(f[p][L][q],f[p][R-bin[q]+1][q]); 101 } 102 103 int query(int x,int y) 104 { 105 int q=Log[y-x+1]; 106 return min(f[3][x][q],f[3][y-bin[q]+1][q]); 107 } 108 109 void solve(int L) 110 { 111 for(int i=0;i+L<n;i+=L) 112 if(ch[i]==ch[i+L]) 113 { 114 int r=lcp(1,i,i+L); 115 // printf("1 %d %d %d\n",i,i+L,r); 116 int l=lcp(2,n-i,n-i-L); 117 // printf("2 %d %d %d\n",n-i,n-i-L,l); 118 if((l+r)/L+1>mx) {mx=(l+r)/L+1; ans=oo;} 119 if((l+r)/L+1==mx) 120 { 121 int t=query(i-l,i-l+(l+r)%L); 122 // printf("%d %d %d\n",i-l,i-l+(l+r)%L,t); 123 if(t<ans) 124 { 125 ans=t; 126 ansl=save[t]; 127 ansr=ansl+mx*L-1; 128 } 129 } 130 } 131 } 132 133 int main() 134 { 135 //freopen("poj3693.in","r",stdin); 136 //freopen("poj3693.out","w",stdout); 137 bin[0]=1; 138 for(int i=1;i<20;i++) bin[i]=bin[i-1]<<1; 139 Log[0]=-1; 140 for(int i=1;i<=100000;i++) Log[i]=Log[i/2]+1; 141 int cas=0; 142 while(scanf("%s",ch)) 143 { 144 if(ch[0]=='#') break; 145 cas++; 146 printf("Case %d: ",cas); 147 148 init(); 149 n=strlen(ch); 150 for(int i=0;i<n;i++) s[i]=ch[i]-'a'+1; 151 s[n]=0; 152 getsa(s,sa,n+1,100); 153 getheight(s,sa,n); 154 155 for(int i=0;i<n;i++) f[3][i][0]=rank[i]; 156 157 int len=Log[n]; 158 for(int i=2;i<=n;i++) f[1][i][0]=height[i]; 159 for(int i=1;i<=len;i++) 160 for(int j=2;j+bin[i]-1<=n;j++) 161 f[1][j][i]=min(f[1][j][i-1],f[1][j+bin[i-1]][i-1]); 162 for(int i=0;i<=n;i++) g[1][i]=rank[i]; 163 for(int i=0;i<=n;i++) save[i]=sa[i]; 164 165 init(); 166 for(int i=0;i<n;i++) s[i]=ch[n-1-i]-'a'+1; 167 s[n]=0; 168 getsa(s,sa,n+1,100); 169 getheight(s,sa,n); 170 171 for(int i=2;i<=n;i++) f[2][i][0]=height[i]; 172 for(int i=1;i<=len;i++) 173 for(int j=2;j+bin[i]-1<=n;j++) 174 f[2][j][i]=min(f[2][j][i-1],f[2][j+bin[i-1]][i-1]); 175 for(int i=0;i<=n;i++) g[2][i]=rank[i]; 176 177 178 179 for(int i=1;i<=len;i++) 180 for(int j=0;j+bin[i]-1<=n-1;j++) 181 f[3][j][i]=min(f[3][j][i-1],f[3][j+bin[i-1]][i-1]); 182 183 ansl=ansr=1; 184 mx=1; ans=oo; 185 for(int i=0;i<n;i++) 186 if(ch[i]<ch[ansl]){ans=1; ansl=ansr=i;} 187 for(int i=1;i<=n;i++) solve(i); 188 for(int i=ansl;i<=ansr;i++) printf("%c",ch[i]); 189 printf("\n"); 190 } 191 return 0; 192 } 193