我们定义一个字符串的后缀suffix(i)表示从s[i]到s[length(s)]这段子串。 后缀数组（Suffix array）SA[i]中存放着一个排列，满足suffix(sa[i])

输入

一行，为描述中的字符串（仅会出现小写字母）

输出

共两行，每行n个数，第一行为sa[i]，第二行为height[i]，其中每行的数均用空格隔开

样例输入

aabaaaab

样例输出

4 5 6 1 7 2 8 3
0 3 2 3 1 2 0 1

来源/分类

 

[提交] [状态]