提交记录 5444 - Judge Duck Online

用户	题目	状态	得分	用时	内存	语言	代码长度
Moon	1006. 【模板题】后缀排序	Compile Error	0	0 ns	0 KB	C++	1.48 KB

提交时间	评测时间
2018-08-22 21:52:33	2020-08-01 00:17:15

代码

//bzoj 1031
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 400005
using namespace std;
char s[maxn];
int n,c[maxn],sa[maxn],t2[maxn],t1[maxn],h[maxn],rank[maxn];
int *x=t1,*y=t2;

void get_sa()
{
    int m=257;
    memset(t1,-1,sizeof(t1));//ÐÂ¼ÓÄÚÈÝ£¬·Ç³£ÖØÒª£¡£¡£¡£¡£¡
    memset(t2,-1,sizeof(t2));
    for (int i=0;i<m;i++) c[i]=0;
    for (int i=0;i<n;i++) c[x[i]=sa[i]]++;
    for (int i=1;i<m;i++) c[i]+=c[i-1];
    for (int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for (int k=1;k<=n;k<<=1)
    {
        int p=0;
        for (int i=n-k;i<n;i++) y[p++]=i;//µÚ¶þ¹Ø¼ü×ÖÅÅÐò 
        for (int i=0;i<n;i++) if (sa[i]>=k) y[p++]=sa[i]-k;//sa[i]>=kÔòÓÐµÚ¶þ¹Ø¼ü×Ö £¬·ñÔòÃ»ÓÐy 
        for (int i=0;i<m;i++) c[i]=0;//µÚÒ»¹Ø¼ü×ÖÅÅÐò
        for (int i=0;i<n;i++) c[x[y[i]]]++;
        for (int i=1;i<m;i++) c[i]+=c[i-1];
        for (int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;x[sa[0]]=0;
        for (int i=1;i<n;i++)
          x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
        if (p>=n) break;
        m=p;
    }
}

void get_h()
{
    int k=0,j;
    for (int i=0;i<n;i++) rank[sa[i]]=i;
    for (int i=0;i<n;h[rank[i++]]=k)
      for (k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);
}

int main()
{
    //cin>>s;
    scanf("%s",s);
    //s=s+s;
    n=strlen(s);
    for (int i=0;i<n;i++) sa[i]=s[i];
    get_sa();
    get_h(); 
    for (int i=0;i<n;i++) printf("%d ",sa[i]+1);puts("");
    for (int i=1;i<n;++i) printf("%d ",h[i]);
    return 0;
}

评测结果

Compilation

N/A

Compile Error

Score: N/A

显示更多

jp_data/tasks/4b5920e6d34911ea899e00163e04388b/contestant.cpp: In function ‘void get_h()’:
jp_data/tasks/4b5920e6d34911ea899e00163e04388b/contestant.cpp:41:27: error: reference to ‘rank’ is ambiguous
   41 |     for (int i=0;i<n;i++) rank[sa[i]]=i;
      |                           ^~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/utility:70,
                 from /usr/include/c++/9/algorithm:60,
                 from jp_data/tasks/4b5920e6d34911ea899e00163e04388b/contestant.cpp:3:
/usr/include/c++/9/type_traits:1257:12: note: candidates are: ‘template<class> struct std::rank’
 1257 |     struct rank
      |            ^~~~
jp_data/tasks/4b5920e6d34911ea899e00163e04388b/contestant.cpp:8:50: note:                 ‘int rank [400005]’
    8 | int n,c[maxn],sa[maxn],t2[maxn],t1[maxn],h[maxn],rank[maxn];
      |                                                  ^~~~
jp_data/tasks/4b5920e6d34911ea899e00163e04388b/contestant.cpp:42:24: error: reference to ‘rank’ is ambiguous
   42 |     for (int i=0;i<n;h[rank[i++]]=k)
      |                        ^~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/utility:70,
                 from /usr/include/c++/9/algorithm:60,
                 from jp_data/tasks/4b5920e6d34911ea899e00163e04388b/contestant.cpp:3:
/usr/include/c++/9/type_traits:1257:12: note: candidates are: ‘template<class> struct std::rank’
 1257 |     struct rank
      |            ^~~~
jp_data/tasks/4b5920e6d34911ea899e00163e04388b/contestant.cpp:8:50: note:                 ‘int rank [400005]’
    8 | int n,c[maxn],sa[maxn],t2[maxn],t1[maxn],h[maxn],rank[maxn];
      |                                                  ^~~~
jp_data/tasks/4b5920e6d34911ea899e00163e04388b/contestant.cpp:43:25: error: reference to ‘rank’ is ambiguous
   43 |       for (k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);