题目描述
这是一道模板题。
读入一个长度为 $ n $ 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 $ 1 $ 到 $ n $。
输入格式
一行一个长度为 $ n $ 的仅包含大小写英文字母或数字的字符串。
输出格式
第一行 $ n $ 个整数，第 $ i $ 个整数为 $ \text{SA}[i]$。
样例数据
样例 1 输入
ababa样例 1 输出
5 3 1 4 2样例 2 输入
0103210002010200210200101020202222010111样例 2 输出
7 21 8 15 22 35 11 24 1 37 19 13 9 26 28 16 30 3 40 6 23 36 18 12 25 2 39 38 20 14 34 10 27 29 5 17 33 32 31 4子任务
Subtask 1 (25 points), $1 \leq n \leq 10^3$
Subtask 2 (25 points), $1 \leq n \leq 10^4$
Subtask 3 (25 points), $1 \leq n \leq 10^5$
Subtask 4 (25 points), $ 1 \leq n \leq 10 ^ 6 $