> cnt数组开成35和50都是re，开成N（=200010）就a了。。。求解。。。
> 帖代码（基本参照罗穗骞前辈的后缀树组模板）：
> #include<cstdio>
> #include<cstring>
> #include<algorithm>
> using namespace std;
> 
> const int N=200010;
> 
> int n,m,l;
> int r[N],sa[N],h[N];
> int cnt[N],rank[N],x[N],y[N];
> char s[N];
> 
> int cmp(int a,int b,int j) {return y[a]==y[b]&&y[a+j]==y[b+j];}
> void da(int n,int m) {
> 	int i,j,p=1;
> 	memset(cnt,0,sizeof cnt);
> 	for (i=0;i<n;i++) cnt[x[i]=r[i]]++;
> 	for (i=1;i<m;i++) cnt[i]+=cnt[i-1];
> 	for (i=n-1;i>=0;i--) sa[--cnt[x[i]]]=i;
> 	for (j=1;p<n;j<<=1,m=p) {
> 		for (p=0,i=n-j;i<n;i++) y[p++]=i;
> 		for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;
> 		#define xi x[y[i]]
> 		memset(cnt,0,sizeof cnt);
> 		for (i=0;i<n;i++) cnt[xi]++;
> 		for (i=1;i<m;i++) cnt[i]+=cnt[i-1];
> 		for (i=n-1;i>=0;i--) sa[--cnt[xi]]=y[i];
> 		for (swap(x,y),x[sa[0]]=0,p=i=1;i<n;i++)
> 		x[sa[i]]= cmp(sa[i-1],sa[i],j)? p-1:p++;
> 	}
> }
> void calh(int n) {
> 	int i,j,k=0;
> 	for (i=1;i<=n;i++) rank[sa[i]]=i;
> 	for (i=0;i<n;h[rank[i++]]=k)
> 	for (k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
> }
> 
> int solve() {
> 	int ans=0;
> 	for (int i=1;i<=n+m+1;i++)
> 	if (h[i]>ans) {
> 		if (sa[i-1]<n&&sa[i]>n) ans=h[i];
> 		if (sa[i]<n&&sa[i-1]>n) ans=h[i];
> 	}
> 	return ans;
> }
> 
> int main() {
> //	freopen("test.in","r",stdin);
> 	scanf("%s",s),n=strlen(s);
> 	for (int i=0;i<n;i++) r[i]=s[i]-'a'+1;r[n]=28;
> 	scanf("%s",s),m=strlen(s);
> 	for (int i=0;i<m;i++) r[i+n+1]=s[i]-'a'+1;r[n+m+1]=0;
> 	da(n+m+2,30);
> 	calh(n+m+1);
> 	printf("%d\n",solve());
> 	return 0;
> }

• Re:为什么会RE？ (61) 27rabbit 2017-08-08 17:08:44