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

## 为什么会RE？

Posted by Dragoenix at 2015-03-14 18:13:32 on Problem 2774 and last updated at 2015-03-14 18:15:44
```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: