#3095. 「SNOI2019」字符串

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给出一个长度为 n 的由小写字母组成的字符串 a ,设其中第 i 个字符为 a_i (1\le i\le n)

设删掉第 i 个字符之后得到的字符串为 s_i ,请按照字典序对 s_1,s_2,\cdots,s_n 从小到大排序。若两个字符串相等,则认为编号小的字符串字典序更小。

输入格式

第一行一个整数 n

第二行一个长为 n 的由小写字母组成的字符串 a

输出格式

输出一行 n 个整数 k_1, k_2, \dots , k_n ,用空格隔开。表示 s_{k_1}< s_{k_2} < \dots < s_{k_n}

样例

样例输入 1

7
aabaaab

样例输出 1

3 7 4 5 6 1 2

样例解释 1

\begin{align} s_1 = s_2 & = abaaab \nonumber \\ s_3 & = aaaaab \nonumber \\ s_4 = s_5 = s_6 & = aabaab \nonumber \\ s_7 & = aabaaa \nonumber \end{align}

样例 2

见附加文件。

样例 3

见附加文件。

数据范围与提示

对于所有数据, 1\le n\le 10^6

  • 对于 10\% 的数据, 1 \le n \le 2000

  • 对于另外 20\% 的数据, 1 \le n \le 10^5 且任意两个相邻字符 a_i,a_{i+1} 不相等;

  • 对于另外 30\% 的数据, 1 \le n \le 10^5

  • 对于余下 40\% 的数据,无特殊限制。