Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

## Re:为什么会RE？

Posted by a_lazy_student at 2015-03-15 16:33:40 on Problem 2774
In Reply To:为什么会RE？ Posted by:Dragoenix at 2015-03-14 18:13:32
```> 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;
> }
```

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator