#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
int n, *rk, *ork, rid[N], pool[2][N], sa[N], cnt[N], id[N], h[N], tp;
char s[N];
inline int eq(int x, int y, int len) { return ork[x]==ork[y]&&ork[x+len]==ork[y+len]; }
inline void SA(void)
{
rk=pool[0], ork=pool[1];
for(int i=1; i<=n; ++i) ++cnt[rk[i]=s[i]-'a'+1];
for(int i=1; i<=26; ++i) cnt[i]+=cnt[i-1];
for(int i=1; i<=n; ++i) sa[cnt[rk[i]]--]=i;
for(int len=1, lim=0; lim!=n; len<<=1)
{
if(!lim) lim=26;
tp=0;
for(int i=n-len+1; i<=n; ++i) id[++tp]=i;
for(int i=1; i<=n; ++i) if(sa[i]>len) id[++tp]=sa[i]-len;
std::fill(cnt+1, cnt+lim+1, 0);
for(int i=1; i<=n; ++i) ++cnt[rk[i]];
for(int i=1; i<=lim; ++i) cnt[i]+=cnt[i-1];
for(int i=1; i<=n; ++i) rid[i]=rk[id[i]];
for(int i=n; i; --i) sa[cnt[rid[i]]--]=id[i];
std::swap(rk, ork);
lim=0;
for(int i=1; i<=n; ++i)
{
if(i==1||(!eq(sa[i-1], sa[i], len))) rk[sa[i]]=++lim;
else rk[sa[i]]=lim;
}
}
}
inline void gheight(void)
{
for(int i=1, k=0; i<=n; ++i)
{
if(rk[i]==1) continue;
if(k) --k;
int j=sa[rk[i]-1];
while(s[i+k]==s[j+k]) ++k;
h[rk[i]]=k;
}
}
int main()
{
scanf("%s", s+1);
n=strlen(s+1);
SA();
gheight();
for(int i=1; i<=n; ++i) printf("%d ", sa[i]);
puts("");
for(int i=2; i<=n; ++i) printf("%d ", h[i]);
return 0;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Subtask #1 Testcase #1 | 11.36 us | 48 KB | Wrong Answer | Score: -100 | 显示更多 |
Subtask #1 Testcase #2 | 15.59 us | 48 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 14.15 us | 48 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 16.58 us | 48 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 17.22 us | 48 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 16.91 us | 48 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 29.685 ms | 3 MB + 508 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 46.352 ms | 3 MB + 728 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 32.071 ms | 3 MB + 596 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 20.752 ms | 2 MB + 380 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 21.515 ms | 2 MB + 420 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 38.251 ms | 3 MB + 792 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 36.963 ms | 3 MB + 816 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #14 | 33.378 ms | 3 MB + 624 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #15 | 33.094 ms | 3 MB + 628 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #16 | 37.322 ms | 3 MB + 792 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #17 | 37.097 ms | 3 MB + 792 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #18 | 37.373 ms | 3 MB + 792 KB | Accepted | Score: 0 | 显示更多 |