Under construction

Still being built. Things may change

Suffix array 2

Time limit2sMemory limit512 MB

Summary
Sort all suffixes of a string lexicographically and output the starting index of each suffix in sorted order.
Level

Medium7 of 10

Topics
String, Sorting, String matching
Solved
No attempts yet

Problem

The suffix array of a string SS is the array of all suffixes of SS sorted in lexicographic order.

The string banana has 6 suffixes: banana, anana, nana, ana, na, a. Sorted lexicographically they are a, ana, anana, banana, na, nana.

Each suffix is numbered by the position of its first character, counting from 0. So banana is suffix 0 and ana is suffix 3.

Given a string SS, sort all of its suffixes in lexicographic order and print the suffix numbers in that order.

Input

The first line contains the string SS. SS consists of lowercase letters only, and its length is at least 1 and at most 100,000.

Output

Print the suffix numbers, one per line, in the lexicographic order of the suffixes.

Hint

For SS = abcdabcabb, the sorted suffixes and their numbers are:

  • 7: abb
  • 4: abcabb
  • 0: abcdabcabb
  • 9: b
  • 8: bb
  • 5: bcabb
  • 1: bcdabcabb
  • 6: cabb
  • 2: cdabcabb
  • 3: dabcabb

Examples6

  1. Example 1

    Input
    abcdabcabb
    Expected output
    7
4
0
9
8
5
1
6
2
3

  2. Example 2

    Input
    banana
    Expected output
    5
3
1
0
4
2

  3. Example 3

    Input
    a
    Expected output
    0

  4. Example 4

    Input
    ab
    Expected output
    0
1

  5. Example 5

    Input
    ba
    Expected output
    1
0

  6. Example 6

    Input
    mississippi
    Expected output
    10
7
4
1
0
9
8
6
3
5
2