题目描述
这是一道模板题。
读入一个长度为
n
n 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为
1
1 到
n
n。
输入
一行一个长度为
n
n 的仅包含大小写英文字母或数字的字符串。
输出
第一行
n
n 个整数，第
i
i 个整数为
\text{SA}[i]
SA[i]。
样例输入
ababa
样例输出
5 3 1 4 2
提示
数据范围与提示
1 \leq n \leq 10 ^ 6
1≤n≤106
来源/分类
字符串 后缀数组 数据结构