TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5640
  • Problem
  • P5640【SNOI2019 day1】字符串
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,256m
    Description

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

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

    Input Format

    第一行一个整数 \(n\)

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

    Output Format

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

    Sample Input

    7
    aabaaab

    Sample Output

    3 7 4 5 6 1 2

    Hint

    对于所有数据,$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%$ 的数据,无特殊限制。

    样例解释 1

    点击此处下载大样例