| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 992 | Accepted: 408 |
Description
Input
Output
Sample Input
2 Tady nejsou zadni mimozemstani. Lide tady take nejsou. Ja do lesa nepojedu. V sobotu pojedeme na vylet.
Sample Output
Nejdelsi spolecny retezec ma delku 7. Nejdelsi spolecny retezec ma delku 5.
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=20005; char buf[MAXN]; int rnk[MAXN]; int tmp[MAXN]; int sa[MAXN]; int lcp[MAXN]; int len,k; bool comp(int i,int j) { if(rnk[i]!=rnk[j]) return rnk[i]<rnk[j]; else { int ri=(i+k<=len)?rnk[i+k]:-1; int rj=(j+k<=len)?rnk[j+k]:-1; return ri<rj; } } void getsa() { memset(rnk,0,sizeof(rnk)); memset(tmp,0,sizeof(tmp)); memset(sa,0,sizeof(sa)); len=strlen(buf); for(int i=0;i<len;i++) { sa[i]=i; rnk[i]=buf[i]-‘a‘; } sa[len]=len; rnk[len]=-1; for(k=1;k<=len;k*=2) { sort(sa,sa+len+1,comp); tmp[sa[0]]=0; for(int i=1;i<=len;i++) { tmp[sa[i]]=tmp[sa[i-1]]+(comp(sa[i-1],sa[i])?1:0); } for(int i=0;i<=len;i++) { rnk[i]=tmp[i]; } } } void getlcp() { getsa(); memset(rnk,0,sizeof(rnk)); memset(lcp,0,sizeof(lcp)); for(int i=0;i<=len;i++) { rnk[sa[i]]=i; } int h=0; lcp[0]=0; for(int i=0;i<len;i++) { int j=sa[rnk[i]-1]; if(h>0) h--; for(;j+h<len&&i+h<len;h++) if(buf[j+h]!=buf[i+h]) break; lcp[rnk[i]-1]=h; } } int T; char ss[MAXN]; int main() { scanf("%d",&T); getchar(); while(T--) { memset(buf,0,sizeof(buf)); memset(ss,0,sizeof(ss)); gets(buf); int l=strlen(buf); buf[l]=‘$‘; gets(ss); strcat(buf,ss); getlcp(); int ans=0; for(int i=0;i<len;i++) if((sa[i]<l)!=(sa[i+1]<l)) ans=max(ans,lcp[i]); printf("Nejdelsi spolecny retezec ma delku %d.\n",ans); } return 0; }
原文：http://www.cnblogs.com/program-ccc/p/5231936.html