因为本人几乎不会后缀数组，所以遇到这种SA的模板题也要拿SAM解决。
还是有一点思维难度的。
首先按照国际惯例，建反串的SAM。
然后对于这个反串，我们考虑两个前缀哪一个字典序小：因为是串是反的，所以要从后往前比较，那么第一个不相同的字符一定是两个前缀在后缀树上的节点的lca的前一位。记其中一个节点的任意一个endpos的位置是(End[i])，lca的长度是(len[x])，那么这个字符就是(s[n - (End[i] - len[x])])。
这样对于后缀树上的每一个节点，定义(tp[i] = s[n - (End[i] - len[link[i]])] - 'a')，然后以(tp[i])为关键字进行基数排序就好了。
最后建出一棵新的树，在上面dfs一遍即可。
luogu的板儿字符集太大，会MLE，用map又TLE了，而且不想手写哈希表，于是就没放链接。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<assert.h>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1.1e6 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen("ha.in", "r", stdin);
freopen("ha.out", "w", stdout);
#endif
}
int n;
char s[maxn];
int ans[maxn], acnt = 0;
struct Edge
{
int nxt, to;
}e[maxn << 1];
int head[maxn << 1], ecnt = -1;
In void addEdge(int x, int y)
{
e[++ecnt] = (Edge){head[x], y};
head[x] = ecnt;
}
struct Sam
{
int las, cnt;
int tra[maxn << 1][27], link[maxn << 1], len[maxn << 1], id[maxn << 1], End[maxn << 1];
In void init() {id[0] = link[las = cnt = 0] = -1;}
In void insert(int c, int x)
{
int now = ++cnt, p = las;
End[now] = len[now] = len[p] + 1, id[now] = x;
while(~p && !tra[p][c]) tra[p][c] = now, p = link[p];
if(p == -1) link[now] = 0;
else
{
int q = tra[p][c];
if(len[q] == len[p] + 1) link[now] = q;
else
{
int clo = ++cnt; id[clo] = -1;
memcpy(tra[clo], tra[q], sizeof(tra[q]));
len[clo] = len[p] + 1, End[clo] = len[q];
link[clo] = link[q], link[q] = link[now] = clo;
while(~p && tra[p][c] == q) tra[p][c] = clo, p = link[p];
}
}
las = now;
}
int tp[maxn << 1], pos[maxn << 1], buc[maxn << 1];
In void solve()
{
for(int i = 1; i <= cnt; ++i) tp[i] = s[n - End[i] + len[link[i]]] - 'a', ++buc[tp[i]];
for(int i = 1; i <= cnt; ++i) buc[i] += buc[i - 1];
for(int i = 1; i <= cnt; ++i) pos[buc[tp[i]]--] = i;
for(int i = cnt; i; --i) addEdge(link[pos[i]], pos[i]);
//按tp的权值从大到小加边，这样dfs的时候就是从小到大
}
In void dfs(int now)
{
if(~id[now]) ans[++acnt] = id[now];
forE(i, now, v) dfs(v);
}
In void _Print()
{
for(int i = 1; i <= cnt; ++i) printf("now:%d fa:%d len:%d End:%d tp:%d
", i, link[i], len[i], End[i], tp[i]);
}
}S;
int main()
{
// MYFILE();
Mem(head, -1);
scanf("%s", s);
n = strlen(s); S.init();
for(int i = n - 1; i >= 0; --i) S.insert(s[i] - 'a', i);
S.solve(), S.dfs(0);
// S._Print();
for(int i = 1; i <= acnt; ++i) write(ans[i]), space; enter;
return 0;
}