当前位置:首页 > 排序 > 正文
九度OJ1099后缀子串排序
4256+

题目大意:多组数据,每组数据一个字符串,请分别对每个字符串的后缀(含自己)进行排序输出。

时间限制: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]来表示,排序后一次输出。

程序实现

About

坚决不Copy代码!

本文标签:,,,

九度OJ1099后缀子串排序:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!