多组数据，求两个字符串最长连续匹配的任意子串。 连接两个字符串，在衔接处加一个比任意字符都大的一个字符，这样第一个串越靠近衔接处的开头的后缀就会在sa里面离你要匹配的串更远，因为是按字典序排序的，这样就可以保证答案的正确性了。 sa里面和你相邻的绝对是和你相似度最高的，就是连续匹配前缀最长的。
x是第一关键字，y是第二关键字 x的下标是后缀开始的位置，值是排名 y和sa的下标是排名，值是后缀开始的位置
hi[i]代表排名第 i 的后缀和排名第 i-1 的后缀的最长公共前缀
#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXN 200010 #define mod 1000010 int n1,ans,x[MAXN],y[MAXN],mv[MAXN],ms[MAXN],sa[MAXN],hi[MAXN]; char c[MAXN]; int min(int x1,int y1){ return x1>y1?y1:x1; } void makesa(int n,int m){ int i,j,l,p; for(i=1;i<=m;i++) ms[i]=0; for(i=1;i<=n;i++) ms[x[i] = c[i]-'a'+1]++; for(i=2;i<=m;i++) ms[i]+=ms[i-1]; for(i=n;i>=1;i--) sa[ms[x[i]]--]=i; for(l=1;p<n;l<<=1,m=p) { for(p=0,i=n-l+1;i<=n;i++) y[++p]=i; for(i=1;i<=n;i++) if(sa[i]>l) y[++p]=sa[i]-l; for(i=1;i<=n;i++) mv[i]=x[y[i]]; for(i=1;i<=m;i++) ms[i]=0; for(i=1;i<=n;i++) ms[mv[i]]++; for(i=2;i<=m;i++) ms[i]+=ms[i-1]; for(i=n;i>=1;i--) sa[ms[mv[i]]--]=y[i]; for(i=1;i<=n;i++) y[i]=x[i]; for(p=1,x[sa[1]]=1,i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+l]==y[sa[i-1]+l])?p:++p; } } void makehi(int n){ int i,j=0,k; for(i=1;i<=n;i++){ j<=1?j=0:j--; k=sa[x[i]-1]; while(c[i+j]==c[k+j]) j++; hi[x[i]]=j; } } int main(){ int i,j,n,m=30; while(~scanf("%s",c+1)){ ans=0; n=strlen(c+1); n1=n+1; c[n1]='z'+2; scanf("%s",c+2+n); n=strlen(c+1); makesa(n,m); makehi(n); for(i=2;i<=n;i++) if(hi[i]>ans){ if(1<=sa[i-1] && sa[i-1]<=n1 && n1<sa[i] && sa[i]<=n) ans=hi[i]; if(1<=sa[i] && sa[i]<=n1 && n1<sa[i-1] && sa[i-1]<=n) ans=hi[i]; } printf("%d\n",ans); } return 0; } /* yeshowmuchiloveyoumydearmotherreallyicannotbelieveit yeaphowmuchiloveyoumydearmother */