#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
int n, rk[N], sa[N], cnt[N], x[N], y[N], h[N];
char s[N];
inline void proc(char *s, int n)
{
for(int i=1; i<=n; ++i) rk[i]=s[i]-'a'+1;
for(int len=1; len<=n; len<<=1)
{
for(int i=1; i<=n; ++i) x[i]=rk[i], y[i]=((i+len<=n)?rk[i+len]:0);
std::fill(cnt, cnt+std::max(n, 26)+1, 0);
for(int i=1; i<=n; ++i) ++cnt[y[i]];
for(int i=1; i<=std::max(n, 26); ++i) cnt[i]+=cnt[i-1];
for(int i=1; i<=n; ++i) rk[cnt[y[i]]--]=i;
std::fill(cnt, cnt+std::max(n, 26)+1, 0);
for(int i=1; i<=n; ++i) ++cnt[x[i]];
for(int i=1; i<=std::max(n, 26); ++i) cnt[i]+=cnt[i-1];
for(int i=n; i; --i) sa[cnt[x[rk[i]]]--]=rk[i];
for(int i=1, tp=0; i<=n; ++i) tp+=(x[sa[i]]!=x[sa[i-1]]||y[sa[i]]!=y[sa[i-1]]), rk[sa[i]]=tp;
}
}
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];
for(; i+k<=n&&j+k<=n&&s[i+k]==s[j+k]; ++k);
h[rk[i]]=k;
}
}
int main()
{
scanf("%s", s+1);
n=strlen(s+1);
proc(s, n);
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 | 10.06 us | 40 KB | Wrong Answer | Score: -100 | 显示更多 |
Subtask #1 Testcase #2 | 14.44 us | 44 KB | Accepted | Score: 100 | 显示更多 |
Subtask #1 Testcase #3 | 15.06 us | 44 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #4 | 17.18 us | 44 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #5 | 16.86 us | 44 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #6 | 17.01 us | 44 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #7 | 58.947 ms | 3 MB + 152 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #8 | 58.651 ms | 3 MB + 340 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #9 | 58.571 ms | 3 MB + 204 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #10 | 36.791 ms | 2 MB + 120 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #11 | 36.373 ms | 2 MB + 160 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #12 | 49.11 ms | 3 MB + 532 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #13 | 48.615 ms | 3 MB + 500 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #14 | 57.319 ms | 3 MB + 232 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #15 | 56.923 ms | 3 MB + 248 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #16 | 45.89 ms | 3 MB + 532 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #17 | 45.57 ms | 3 MB + 532 KB | Accepted | Score: 0 | 显示更多 |
Subtask #1 Testcase #18 | 45.772 ms | 3 MB + 532 KB | Accepted | Score: 0 | 显示更多 |