推荐题解:http://t.csdn.cn/RuwQS
//若是不知道字符串哈希模板的可以在我的博客中搜索字符串哈希模板
/*
假设后缀数组id[N];
则id[N]用来记录后缀数组的下标从哪个位置上的字母开始.
例如一个字符串ponoiiipoi则:
id[10] : i(从下标为10的位置开始)
id[9] : op(从下标为9的位置开始)
id[8] : poi
id[7] : ipoi
id[6] : iipoi
id[5] : iiipoi
id[4] : oiiipoi
id[3] : noiiipoi
id[2] : onoiiipoi
id[1] : ponoiiipoi
这样做是为了方便排序
1:如何将后缀数组按从小到大排序?
{
利用二分查找找出每个后缀数组的最大前缀,然后比较最大前缀的后面一位数即可
}
#include <cstdio>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N = 300010, base = 131, MIN = -0x3f3f3f3f;
int n;
int id[N];
char str[N];
ULL h[N], p[N];
ULL get(int l, int r)//字符串哈希模板
{
return h[r] - h[l - 1] * p[r - l + 1];
}
int get_profix(int a, int b)//得到后缀数组的最大前缀和
{
int l = 0, r = min(n - a + 1, n - b + 1);//计算前缀和数组的长度.比如当n = 10, a = 2时则
while (l < r)//则后缀数组所对应的字符串为onoiiipoi长度为n - a + 1 == 9;
{
int mid = l + r + 1 >> 1;//mid枚举的是前缀和的长度
if (get(a, a + mid - 1) == get(b, b + mid - 1)) l = mid;//若他们前缀和的长度相等,则扩大搜索范围
else r = mid - 1;//否则减小范围
}
return l;
}
bool cmp(int a, int b)//将所有后缀数组的从小到大排序;
{
int lca = get_profix(a, b);
int av = a + lca > n ? MIN : str[a + lca];//若最大前缀和的最后一位超过了后缀和数组,
int bv = b + lca > n ? MIN : str[b + lca];//在前面字母都相同的情况下a比b少了一位元素
return av < bv; //则a肯定是小于b的,将a置为无穷小即可
}
int main()
{
cin >> str + 1;
n = strlen(str + 1);
p[0] = 1;
for (int i = 1; i <= n; i ++ )//字符串哈希模板
{
h[i] = h[i - 1] * base + str[i] - 'a' + 1;
p[i] = p[i - 1] * base;
id[i] = i;
}
sort(id + 1, id + n + 1, cmp);//将所有后缀数组的从小到大排序;
for (int i = 1; i <= n; i ++ ) printf("%d ", id[i] - 1);//题目要求下标从0开始我们的下标是从1开始
puts("");
for (int i = 1; i <= n; i ++ )
if (i == 1) printf("0 ");
else printf("%d ", get_profix(id[i - 1], id[i]));
puts("");
return 0;
}