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？ (1613) a_lazy_student 2015-03-15 16:33:40
  • Re:为什么会RE？ (61) 27rabbit 2017-08-08 17:08:44