给出一个长度为n的字符串({s_i}),定义它的后缀为一个i，表示子串(s[isim n])，现在请维护出(SA[i])为存储后缀的数组，但是按照其对应的子串的字典序排序，(Height[i])为第i个后缀和第i+1个后缀对应的子串公共前缀的长度，(nleq 3 imes 10^5)。
解
最直接的思路是对后缀数组直接排序，问题在于时间复杂度为(O(n^2log(n))),我们可以尝试优化其中的(O(n))的比较，因为子串的比较，维护出前缀hash值，以后，可以通过二分找到第一个前缀不相等的位置，注意不存在这个位置需要特判，然后向后比较一个，就能知道两个子串的大小了，这样比较就优化到了(log(n))。
而至于最长公共前缀同样的方法二分，于是可以做到时间复杂度(nlog(n)^2)。
参考代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define il inline
#define ri register
#define ll long long
#define ull unsigned ll
#define Size 300500
#define jzm 19260817
using namespace std;
char s[Size];
int sl,suf[Size];
ull base[Size],hs[Size];
il void prepare();
il bool comp(const int,const int);
il int ask(int,int),dfs(int,int);
template<class free>il free Min(free,free);
int main(){
scanf("%s",s+1);
sl=strlen(s+1),prepare();
for(int i(1);i<=sl;++i)suf[i]=i;
sort(suf+1,suf+sl+1,comp);
for(int i(1);i<=sl;++i)
printf("%d ",suf[i]-1);
putchar('
'),putchar(48);
for(int i(2);i<=sl;++i)
printf(" %d",dfs(suf[i],suf[i-1]));
return 0;
}
il bool comp(const int x,const int y){
int p(dfs(x,y));
if(x+p-1>=sl||y+p-1>=sl)return x>y;
return s[x+p]<s[y+p];
}
template<class free>
il free Min(free a,free b){
return a<b?a:b;
}
il int dfs(int p1,int p2){
int l(1),r(Min(sl-p1+1,sl-p2+1)),mid;
while(l<=r){mid=l+r>>1;
if(ask(p1,p1+mid-1)==ask(p2,p2+mid-1))l=mid+1;
else r=mid-1;
}return r;
}
il int ask(int l,int r){
return hs[r]-hs[l-1]*base[r-l+1];
}
il void prepare(){base[0]=1;
for(int i(1);i<=sl;++i)
base[i]=base[i-1]*jzm,
hs[i]=hs[i-1]*jzm+s[i];
}