题目描述

字符串s="aabaaaab"有8个后缀串，分别是 aabaaaab  abaaaab baaaab aaaab  aaab  aab ab b 按字典序他们的顺序分别是 4    6    8    1    2    3    5    7 后缀数组里的sa数组定义如下： SA[i]=k,表示后缀串里排名第i的后缀是从k开始的后缀串 例如： sa[1]=4,表示排名第一的是从第4个字符开始的后缀串，也就是 aaaab 给你一个字符串，请打印出字符串的后缀数组

输入格式

若干行测试数据，一行一个字符串S，s长度∈[1,1e6]，s里的字符可以是数字和英文字母

输出格式

这个字符串的后缀数组值

aabaaaab

4 5 6 1 7 2 8 3