后缀排序【模板】

题目描述:

这是一道模板题。

读入一个长度为 n 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 1 到 n 。

输入格式:

一行一个长度为 n 的仅包含大小写英文字母或数字的字符串。

输出格式:

第一行 n 个整数，第 i个整数为 SA[i]。

样例输入:

ababa

样例输出:

5 3 1 4 2

提示:

1≤n≤10​^6​​

时间限制: 1000ms
空间限制: 256MB

---