SA萌新求助
查看原帖
SA萌新求助
200044
JS_TZ_ZHR楼主2021/7/20 20:55

为什么这个错了啊,没有数据死活找不到错误

#include<bits/stdc++.h>
#define N 600005
using namespace std;
int n,m,pos,sa[N],rk[N],cnt[N],ork[N],h[N],p[N],ans,k;
char s[N];
signed main(){
    cin>>(s+1);
    pos=n=strlen(s+1);
    s[n+1]='@';
    cin>>(s+n+2);
    n=strlen(s+1);
    m=max(n,300);
    for(int i=1;i<=n;i++)++cnt[rk[i]=s[i]];
    for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;
    for(int w=1;w<=n;w<<=1){
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)p[i]=sa[i];
        for(int i=1;i<=n;i++)++cnt[rk[p[i]+w]];
        for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;i--)sa[cnt[rk[p[i]+w]]--]=p[i];
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)p[i]=sa[i];
        for(int i=1;i<=n;i++)++cnt[rk[p[i]]];
        for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;i--)sa[cnt[rk[p[i]]]--]=p[i];
        memcpy(ork,rk,sizeof(rk));
        for(int p=0,i=1;i<=n;i++){
            if(ork[sa[i]]==ork[sa[i-1]]&&ork[sa[i]+w]==ork[sa[i-1]+w])rk[sa[i]]=p;
            else rk[sa[i]]=++p;
        }
    }
    for(int i=1;i<=n;i++){
        if(rk[i]==1)k=0;
        if(k)k--;
        while(s[i+k]==s[sa[rk[i]-1]+k])k++;
        h[rk[i]]=k;
    }
    for(int i=1;i<=n;i++)if((sa[i]<=pos&&sa[i-1]>pos)||(sa[i]>pos&&sa[i-1]<=pos))ans=max(ans,h[i]);
    cout<<ans<<endl;
}
2021/7/20 20:55
加载中...