题目描述：
后缀数组 (SA) 是一种重要的数据结构，通常使用倍增或者DC3算法实现，这超出了我们的讨论范围。
在本题中，我们希望使用快排、Hash与二分实现一个简单的O(nlog^2n)的后缀数组求法。
详细地说，给定一个长度为 n 的字符串S（下标 0~n-1），我们可以用整数 k(0≤k<n) 表示字符串S的后缀 S(k~n-1)。
把字符串S的所有后缀按照字典序排列，排名为 i 的后缀记为 SA[i]。额外地，我们考虑排名为 i 的后缀与排名为 i-1 的后缀，把二者的最长公共前缀的长度记为 Height[i]。我们的任务就是求出SA与Height这两个数组。
输入格式
输入一个字符串，其长度不超过30万。
输出格式
第一行为数组SA，相邻两个整数用1个空格隔开。
第二行为数组Height，相邻两个整数用1个空格隔开，我们规定Height[1]=0。
输入样例：
ponoiiipoi输出样例：
9 4 5 6 2 8 3 1 7 0 0 1 2 1 0 0 2 1 0 2分析：
本题看起来挺复杂，实际考察的都是前几题考过的字符串Hash + 二分，并没有新的知识点。
对于样例ponoiiipoi，其后缀一共有ponoiiipoi，onoiiipoi，noiiipoi，oiiipoi，iiipoi，iipoi，ipoi，poi，oi，i十个，分别用其首元素所在的下标0 - 9表示，可以发现，对上面的后缀字符串按照字典序排序，则i字典序最小，iiipoi第二小，其下标依次为9和4，其它的类似，所以第一行输出的是排序后的后缀顺序9 4 5 6 2 8 3 1 7 0。对于i，没有比它更小的后缀了，所以其与前面元素公共前缀长度为0，对于iiipoi，与其前面元素i公共前缀长度为1，所以第二行依次输出0 1 2 1 0 0 2 1 0 2，以此来表示按字典序排序后相邻两个元素公共前缀的长度。
首先考虑如何对这么多后缀字符串进行排序，我们知道，一般的排序是需要O（nlogn）时间的，而对于两个字符串，比较下大小的时间复杂度就为O（n），对字符串数组排序的话总的时间复杂度就为O（n^2 * logn）了。考虑用字符串Hash + 二分来将两个字符串比较大小的过程优化到O（logn）。例如abcfe和abcde，对其分别做了hash映射后，l = 0，r =,4，mid = 2，通过字符串hash值发现abc = abc，于是l = 2，mid = 3，发现abcf ！= abcd，于是r = mid - 1 = 2，此时l = r，循环终止，找到了最长公共前缀的长度为3。于是我们可以直接比较下标为3的字符f和d，得到abcfe > abcde。倘若一个字符串为另一个字符串的前缀呢？比如比较abc和abcd时，公共长度为3，abcd的下标为3的字符是d，而abc的下标为3的字符就是空的了，为了处理这种情况，就直接将abc的下标为3的元素设为无穷小，就可以比较出二者的大小了。
#include <iostream> #include <cstring> #include <algorithm> #include <climits> using namespace std; typedef unsigned long long ull; const int maxn = 300010,base = 131; int n; char str[maxn]; ull h[maxn],p[maxn]; int sa[maxn],height[maxn]; int get(int l,int r){ return h[r] - h[l - 1] * p[r - l + 1]; } int max_common_prefix(int a,int b){ int l = 0,r = min(n - a + 1,n - b + 1); while(l < r){ int mid = l + r + 1 >> 1; if(get(a,a + mid - 1) != get(b,b + mid - 1)) r = mid - 1; else l = mid; } return l; } bool cmp(int a,int b){ int l = max_common_prefix(a,b); int av = a + l > n ? INT_MIN : str[a + l]; int bv = b + l > n ? INT_MIN : str[b + l]; return av < bv; } int main(){ scanf("%s",str + 1); n = strlen(str + 1); p[0] = 1; for(int i = 1;i <= n;i++){ h[i] = h[i - 1] * base + str[i] - '0'; p[i] = p[i - 1] * base; sa[i] = i; } sort(sa + 1,sa + 1 + n,cmp); for(int i = 1;i <= n;i++) printf("%d ",sa[i] - 1); puts(""); for(int i = 1;i <= n;i++){ if(i == 1) printf("0 "); else{ printf("%d ",max_common_prefix(sa[i - 1],sa[i])); } } puts(""); return 0; }
