-时间限制:1秒 空间限制:32768K
题目描述 对于一个字符串,将其后缀子串进行排序,例如grain 其子串有: grain rain ain in n 然后对各子串按字典顺序排序,即: ain,grain,in,n,rain
输入描述: 每个案例为一行字符串。 输出描述: 将子串排序输出 示例1 输入 grain
输出 ain grain in n rain
本题目可以暴力排序解决,暴力时优化方法是用指针代替子数组的复制,这里我为了学习字符串知识使用后缀数组完成,代码如下:
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int Maxn = 1005; int sa[Maxn], Rank[Maxn], tmp[Maxn]; int n, k; bool compareSa(const int i, const int j) { if(Rank[i]!=Rank[j]) return Rank[i]<Rank[j]; int ri = (i+k>n)?-1:Rank[i+k]; int rj = (j+k>n)?-1:Rank[j+k]; return ri<rj; } void getSa(const char *str) { n = strlen(str); for(int i = 0; i <= n; ++i) { sa[i] = i; Rank[i] = str[i]; //纯字符串也可直接用ASCII编码 } for(k = 1; k <= n; k*=2) { sort(sa, sa+n+1, compareSa); tmp[sa[0]] = 0; for(int i = 1; i <= n; ++i) tmp[sa[i]] = tmp[sa[i-1]] + (compareSa(sa[i-1], sa[i])?1:0); for(int i = 0; i <= n; ++i) Rank[i] = tmp[i]; } } int main() { char str[Maxn]; while(cin >> str) { getSa(str); for(int i = 1; i <= n; ++i) { for(int j = sa[i]; j < n; ++j) cout << str[j]; cout << endl; } } return 0; }这里求Sa和Rank数组我使用的是《挑战程序设计竞赛(第2版)》一书中的求法,对网上的求法看了很长一段时间没看进去!