```
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
char s[N];
int n,sa[N],rk[N],oldrk[N << 1],id[N],px[N],cnt[N];
// px[i] = rk[id[i]]（用于排序的数组所以叫 px）
bool cmp(int x, int y, int w) {
return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}
int main() {
int i, m = 300, p, w;
scanf("%s",s+1);
n = strlen(s+1);
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 i=1;i<=n;i++) cout<<sa[i]<<' ';
cout<<endl;
for (w = 1; w < n; w <<= 1, m = p) { // m=p 就是优化计数排序值域
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;
memset(cnt, 0, sizeof(cnt));
for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
memcpy(oldrk, rk, sizeof(rk));
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
for (i = 1; i <= n; ++i) printf("%d ", sa[i]);
return 0;
}
```
by chen_qian @ 2021-03-09 11:56:59
这是 oiwiki 上的
by chen_qian @ 2021-03-09 11:57:15
@[chen_qian](/user/128870)
```cpp
m = p
```
by Xopered @ 2021-03-09 12:41:46
@[无限天空](/user/329589) 谢谢，AC了
by chen_qian @ 2021-03-09 14:26:27
@[无限天空](/user/329589)
但是原文说这里是为了优化值域但是原文说这里是为了优化值域
by chen_qian @ 2021-03-09 14:27:39
不用也行的吧？
by chen_qian @ 2021-03-09 14:28:10
@[chen_qian](/user/128870) 不优化的话应该m=n一直不变，300是不够的
by Xopered @ 2021-03-09 14:29:00
哦，谢谢
by chen_qian @ 2021-03-09 14:29:43
@[无限天空](/user/329589)
by chen_qian @ 2021-03-09 14:29:53