学步园

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2774

#include "iostream"<br /> #include "cstring"<br /> using namespace std;<br /> const int MaxN=210000+100;<br /> int SA[MaxN],Rank[MaxN*2],D[MaxN*2],Count_Rank[MaxN*2];<br /> int Height[MaxN];<br /> int N,M,K,Len1,Len2;<br /> char A[MaxN],S[MaxN],S1[MaxN],S2[MaxN];<br /> int B[MaxN],List[MaxN],P;<br /> void input(){<br /> scanf("%s",S+1);<br /> Len1=strlen(S+1);<br /> ++Len1;<br /> S[Len1]='#';<br /> //puts(S+1);<br /> scanf("%s",S+Len1+1);<br /> N=strlen(S+1);<br /> ++N;<br /> S[N]=0;<br /> //puts(S+1);<br /> }<br /> void ssort(){<br /> int i,j,L,k;<br /> memset(D,0,sizeof(D));<br /> memset(SA,0,sizeof(SA));<br /> memset(Rank,0,sizeof(D));<br /> memset(Count_Rank,0,sizeof(D));<br /> sort(A+1,A+N+1);<br /> for(i=1;i <=N;++i) Rank[i]=lower_bound(A,A+N+1,S[i])-A;<br /> for(L=1;L <N; L*=2){<br /> memset(Count_Rank,0,sizeof(Count_Rank));<br /> for(i=1;i <=N;++i) Count_Rank[Rank[i+L]]++;<br /> for(i=1;i <=N;++i) Count_Rank[i]+=Count_Rank[i-1];<br /> for(i=N;i >0; --i) D[Count_Rank[Rank[i+L]]--]=i;<br /> memset(Count_Rank,0,sizeof(Count_Rank));<br /> for(i=1;i <=N;++i) Count_Rank[Rank[i]]++;<br /> for(i=1;i <=N;++i) Count_Rank[i]+=Count_Rank[i-1];<br /> for(i=N;i >0; --i) SA[Count_Rank[Rank[D[i]]]--]=D[i];<br /> memcpy(D,Rank,sizeof(Rank));<br /> Rank[SA[1]]=k=1;<br /> for(i=2;i <=N;++i){<br /> if( D[SA[i]] != D[SA[i-1]] || D[SA[i]+L] !=D[SA[i-1]+L]) k++;<br /> Rank[SA[i]]=k;<br /> }<br /> }<br /> k=0;<br /> for(i=1;i <=N;++i){<br /> if(Rank[i]==N) { Height[N]=k=0; continue;}<br /> j=SA[Rank[i]+1];<br /> for(k=max(k-1,0); S[i+k]==S[j+k];k++);<br /> Height[Rank[i]]=k;<br /> }<br /> }<br /> int main(){<br /> int i,j,k;<br /> input();<br /> //printf("N=%d/n",N);<br /> //puts(S+1);<br /> memcpy(A,S,sizeof(S));<br /> ssort();<br /> int p1,p2,ans=-1;<br /> /*for(int i=1;i <=N;++i)<br /> printf("i=%d %d/n",i,S[i]);*/<br /> /*for(int i=1;i <N;++i){<br /> printf("Height[i]=%d ",Height[i]);<br /> printf("SA[i]=%d SA[i+1]=%d %s/n",SA[i],SA[i+1],S+SA[i]);<br /> }*/<br /> for(int i=1;i <N;++i){<br /> j=SA[i];<br /> if(j <Len1) p1=1;<br /> else p1=-1;<br /> k=SA[i+1];<br /> //printf("j=%d k=%d Height[i]=%d/n",j,k,Height[i]);<br /> if(k <Len1) p2=1;<br /> else p2=-1;<br /> if( p1 * p2< 1 && Height[i]> ans)<br /> ans=Height[i];<br /> }<br /> printf("%d/n",ans);<br /> return 0;<br /> }

将两个字符串连接成一个字符串， 求该字符串的后缀数组， 然后求分别位于两个串中的Height数组的最大值，即为所求答案。