九度OJ1099后缀子串排序
5204+
作者：crxis 发布：2017-07-26 分类：排序
题目大意：多组数据，每组数据一个字符串，请分别对每个字符串的后缀（含自己）进行排序输出。
时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：4622 解决：2065
- 题目描述：
- 对于一个字符串，将其后缀子串进行排序，例如grain
其子串有：
grain
rain
ain
in
n然后对各子串按字典顺序排序，即：
ain,grain,in,n,rain
- 输入：
- 每个案例为一行字符串。
- 输出：
- 将子串排序输出
- 样例输入：
-
grain
- 样例输出：
-
ain grain in n rain
- 来源：
- 2010年上海交通大学计算机研究生机试真题
解题思路
空间限制比较小，将所有子串都存下来比较占用空间（当然数据小空间也够），而且保存所有子串到一个字符数组或者string，需要拷贝，效率比较低，故考虑采用索引排序——用一个数组记录待排序数据的原始编号（索引值），如原来需要排序的数组array是“grain rain ain in n”，他们的编号数组index分别是“1 2 3 4 5”，索引排序时，比较rain和ain，即比较array[ index[2] ]和array[ index[3] ]。
本题具体实现：多组数据，每组数据字符串保存到字符数组s，用n记录字符串长度，a数组记录索引值，排序时定义索引排序的大小，由于这是后缀数组，a[i]、a[j]分别是子串在原来字符串的开头，其结尾相同，故他们可以用s+a[i]和s+a[j]来表示，排序后一次输出。
程序实现
