http://hihocoder.com/problemset/problem/1415
1 #include<cmath> 2 #include<queue> 3 #include<cstdio> 4 #include<vector> 5 #include<cstdlib> 6 #include<cstring> 7 #include<iostream> 8 #include<algorithm> 9 #define N 200010 10 #define RG register 11 #define inf 0x3f3f3f3f 12 #define Inf 99999999999999999LL 13 using namespace std; 14 typedef long long LL; 15 char c[2*N],c1[N],c2[N]; 16 int ans,len,len1,len2,a[N],b[N],sa[N],ssa[N],cnta[N],cntb[N],heit[N],order[N]; 17 inline int Abs(RG const int &a){return a>0?a:-a;} 18 inline int Max(RG const int &a,RG const int &b){return a>b?a:b;} 19 inline int Min(RG const int &a,RG const int &b){return a>b?b:a;} 20 inline int gi(){ 21 RG int x=0;RG bool flag=0;RG char c=getchar(); 22 while((c<'0'||c>'9')&&c!='-') c=getchar(); 23 if(c=='-') c=getchar(),flag=1; 24 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 25 return flag?-x:x; 26 } 27 inline void getsa(){ 28 for (RG int i=1;i<=len;++i) ++cnta[c[i]]; 29 for (RG int i=1;i<=200;++i) cnta[i]+=cnta[i-1]; 30 for (RG int i=len;i;--i) sa[cnta[c[i]]--]=i; 31 order[sa[1]]=1; 32 if(len>1){ 33 for (RG int i=2;i<=len;++i){ 34 order[sa[i]]=order[sa[i-1]]; 35 if(c[sa[i]]!=c[sa[i-1]]) ++order[sa[i]]; 36 } 37 for (RG int now=1;order[sa[len]]<len;now<<=1){ 38 memset(cnta,0,sizeof(cnta)); 39 memset(cntb,0,sizeof(cntb)); 40 for (RG int i=1;i<=len;++i){ 41 ++cnta[a[i]=order[i]]; 42 ++cntb[b[i]=(i+now<=len)?order[i+now]:0]; 43 } 44 for (RG int i=1;i<=len;++i) cntb[i]+=cntb[i-1]; 45 for (RG int i=len;i;--i) ssa[cntb[b[i]]--]=i; 46 for (RG int i=1;i<=len;++i) cnta[i]+=cnta[i-1]; 47 for (RG int i=len;i;--i) sa[cnta[a[ssa[i]]]--]=ssa[i]; 48 order[sa[1]]=1; 49 for (RG int i=2;i<=len;++i){ 50 order[sa[i]]=order[sa[i-1]]; 51 if(a[sa[i]]!=a[sa[i-1]]||b[sa[i]]!=b[sa[i-1]]) ++order[sa[i]]; 52 } 53 } 54 } 55 for (RG int i=1,j=0;i<=len;++i){ 56 if(j) --j; 57 while(c[i+j]==c[sa[order[i]-1]+j]) ++j; 58 heit[order[i]]=j; 59 } 60 } 61 inline void work(){ 62 scanf("%s%s",c1+1,c2+1); 63 len1=strlen(c1+1);len2=strlen(c2+1); 64 for (RG int i=1;i<=len1;++i) c[i]=c1[i]; 65 c[len1+1]='z'+1; 66 for (RG int i=1;i<=len2;++i) c[len1+1+i]=c2[i]; 67 /*scanf("%s",c+1);*/ 68 //cout << c+1 << endl; 69 len=strlen(c+1); 70 getsa(); 71 /*for (RG int i=1;i<=len;++i) cout<<order[i]<<' '; 72 cout<<endl; 73 for (RG int i=1;i<=len;++i) cout<<sa[i]<<' '; 74 cout<<endl; 75 for (RG int i=1;i<=len;++i) cout<<heit[i]<<' '; 76 cout<<endl;*/ 77 for (RG int i=2;i<=len;++i) 78 if(heit[i]>ans){ 79 RG int pren=sa[i-1],bacn=sa[i]; 80 if((pren<=len1&&bacn>=len1+2)||(bacn<=len1&&pren>=len1+2)) 81 ans=heit[i]; 82 } 83 printf("%d ",ans); 84 /*for(int i=1;i<=len;i++){ 85 for(int j=sa[i];j<=len;j++){ 86 cout << c[j] << " "; 87 } 88 cout << " " << heit[i] << endl; 89 }*/ 90 } 91 int main(){ 92 work(); 93 return 0; 94 }