算法竞赛进阶指南，69页， 字符串哈希，二分
本题要点：
1、通过字符串哈希来判断字符串的所有子字符串是否相等；
使用sort 排序，n个字符串排序的比较次数 O(n * log(n)), 长度为n的字符串，比较的次数是n，
如果暴力使用sort ，总的时间复杂度为 O(n^2 * log(n));
2、如果通过二分法来判断连个字符串是否相等，时间复杂度为 O(log(n)) ,总的复杂度为 O(n * log(n) * log(n))；
对于两个后缀字符串，从下标 p和q开始，计算出其公共前缀的长度为 len； 比较 str[p + len] 和 str[q + len]
即可。
二分 长度 len 的过程：
L = 0， R = min(n - p + 1, n - q + 1) + 1 // n - p + 1， 表示 字符串 (从下标p开始的后缀的长度)
mid = (L + R) / 2;
每次判断两个子串是否相等， str[p ~ p + mid - 1] 和 str[q ~ q + mid - 1], 直接通过字符串 哈希值来判断
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int P = 131;
const int MaxN = 300010;
int n;
char str[MaxN];
unsigned long long pre[MaxN]; //各个前缀 的哈希值
unsigned long long p_pow[MaxN];
int sa[MaxN];int calc(int p, int q) //计算两个后缀的最长公共前缀的长度
{
int L = 0, R = min(n - p + 1, n - q + 1) + 1;int mid;int l1 = p, r1, l2 = q, r2;while(L < R){
mid = (L + R) / 2;r1 = p + mid - 1, r2 = q + mid - 1;if(pre[r1] - pre[l1 - 1] * p_pow[r1 - l1 + 1] != pre[r2] - pre[l2 - 1] * p_pow[r2 - l2 + 1]){
R = mid;}else{
L = mid + 1;}}return L - 1;
}bool cmp(int p, int q)
{
int len = calc(p, q);return str[p + len] < str[q + len];
}void init()
{
n = strlen(str + 1);pre[0] = 0;for(int i = 1; i <= n; ++i){
pre[i] = pre[i - 1] * P + str[i] - 'a' + 1; }p_pow[0] = 1;for(int i = 1; i < MaxN; ++i){
p_pow[i] = p_pow[i - 1] * P;}
}void solve()
{
int len = strlen(str + 1);for(int i = 1; i <= len; ++i){
sa[i] = i;}sort(sa + 1, sa + len + 1, cmp);for(int i = 1; i <= len; ++i){
printf("%d", sa[i] - 1);if(i < len){
printf(" ");}else{
printf("\n");}}printf("0");for(int i = 2; i <= len; ++i){
printf(" %d", calc(sa[i], sa[i - 1])); }printf("\n");
}int main()
{
scanf("%s", str + 1);init();solve();return 0;
}/* ponoiiipoi *//* 9 4 5 6 2 8 3 1 7 0 0 1 2 1 0 0 2 1 0 2 */