//#include <bits/stdc++.h>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <limits>
#include <map>
#include <vector>
#include <queue>
#define P pair<int ,int >
#define pb push_back
#define LL long long
#define ft first
#define sd second
#define mp(x,y) make_pair(x,y)
#define db double
//#define int LL
using namespace std;
const int N = 1e5+6;
//const int mod = ;
const int INF =numeric_limits<int >::max();
#define rep(i,x,y) for (int i=x;i<=y;++i)
void read(int &x)
{
x=0;
char ch=getchar();
int f=1;
while (!isdigit(ch)) (ch=='-'?f=-1:0),ch=getchar();
while ( isdigit(ch)) x=x*10+ch-'0',ch=getchar();
x*=f;
}
struct suffix_array
{
//static const int M=
int n,m,cnt[N<<1],sa[N<<1],rk[N<<1],h[N<<1],tp[N<<1],p;
int *x=rk,*y=tp;
char str[N<<1];
void Sort()
{
rep(i,0,m) cnt[i]=0;
rep(i,1,n) ++cnt[x[y[i]]] ;
rep(i,1,m) cnt[i]+=cnt[i-1];
for (int i=n;i>=1;--i) sa[cnt[x[y[i]]]--]=y[i];
}
int cmp(int *f,int x,int y,int w){return f[x]==f[y]&&f[x+w]==f[y+w];}
void SA()
{
rep(i,1,n ) x[i]=str[i],y[i]=i;
m=256;Sort();
for (int w=1;w<=n;w<<=1,m=p)
{
p=0;
rep(i,n-w+1,n) y[++p]=i;
rep(i,1,n) if (sa[i]>w) y[++p]=sa[i]-w;
Sort();swap(x,y);
x[sa[1]]=1;
rep(i,2,n) x[sa[i]] =cmp(y,sa[i],sa[i-1],w) ? p:++p;
}
rep(i,1,n) rk[sa[i]]=i;
for (int j,k=0,i=1;i<=n;h[rk[i++]]=k)
for ( k?--k:0 ,j=sa[rk[i]-1];str[j+k]==str[i+k];++k);
}
}A;
signed main()
{
scanf("%s",A.str+1) ;
A.n=strlen(A.str+1);
A.SA();
rep(i,1,A.n) printf("%d ",A.sa[i]);puts("");
rep(i,2,A.n) printf("%d ",A.h[i]);
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 36.98 us | 60 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #2 | 38.2 us | 60 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 36.86 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 42.72 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 41.4 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 43.54 us | 60 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 57.241 ms | 3 MB + 196 KB | Wrong Answer | Score: -100 | 显示更多 |
Subtask #1 Testcase #8 | 54.667 ms | 3 MB + 384 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 56.745 ms | 3 MB + 248 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 35.7 ms | 2 MB + 136 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 35.147 ms | 2 MB + 176 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 42.292 ms | 3 MB + 444 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 42.417 ms | 3 MB + 544 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #14 | 55.079 ms | 3 MB + 276 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #15 | 54.363 ms | 3 MB + 292 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #16 | 42.18 ms | 3 MB + 444 KB | Wrong Answer | Score: 0 | 显示更多 |
Subtask #1 Testcase #17 | 42.141 ms | 3 MB + 444 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #18 | 42.486 ms | 3 MB + 444 KB | Accepted | Score: 0 | 显示更多 |