后缀数组

定义

后缀排序：
将所有后缀s[i]看作独立的串，然后放在一起按照字典序进行排序

后缀排名 rk[i]：
rk[i]表示后缀s[i]在后缀排序中的排名

后缀数组sa[i]：
sa[i]表示排名第i小的后缀

rk[sa[i]]=i

后缀排序1

用二分hash写一个cmp函数，然后调用sort

复杂度 O(n*logn*logn)

后缀排序2：前缀倍增法

将比较字典序的二分求LCP转化为倍增求LCP

首先等效得认为在字符串的结尾增添无限个空字符串

定义S(i,k)=S[i,i+2^k-1],即以i位置为开头，长度为2^k的子串

只需要将S(i,[$log_2n$]上取整) i=1,2,…,n排序即可

假设当前已经知道了S(i,k)的排序结果，下一步要如何利用他排序S(i,k+1)

可以将S(i,k+1)看成一个两位数，高位是rk[S(i,k)]，地位是rk[S(i+2^k,k)]

基数排序

复杂度O(n)
二元组设为{A,B}
首先统计cntA[x]，表示高位A=x的数字有几个，于是可以确定第i个数字的最终排名一定在范围($\sum_{x=1}^{x<Ai}cntA[x],\sum_{x=1}^{x<=Ai}cntA[x]$)内，记为(sumA[Ai-1],SumA[Ai]]

接下来需要确定每个块(A=x)内数字的顺序

按照低位B从大到小，依次领取排名(利用桶排序)

复杂度 O(n*logn)

后缀排序3：DC3

将所有后缀按照开头下标mod3分类，首先将后缀1，后缀2排序，然后后缀90单独排序，然后再归并起来

复杂度 O(比方法2快一点)

后缀排序4：SA-IS

复杂度 O(n)

后缀数组的性质

设有一组排过序的字符串A=[A1,A2,…,An],要快速求Ai与Aj的LCP

对于任意的k属于[i,j]，LCP(Ai,Aj)=LCP(LCP(Ai,Ak),LCP(Ak,Aj))=min((LCP(Ai,Ak),LCP(Ak,Aj)),进而，LCP(Ai,Aj)=min(LCP(Ai,Ai+1),LCP(Ai+1,Ai+2),…,LCP(Aj-1,aj))

Height数组

Height[i]为后缀i与排名在他按一个的后缀的LCP，即Height[i]=LCP(S[i,n],S[sa[rk[i]-1,n])

结论：
Height[i]>=Height[i-1]-1
证明：
1.Height[i-1]<=1,显然成立

2.Height[i-1]>1

设K1=sa[rk[i-1]-1],n]],K2=sa[rk[i]-1],n]

去掉首字母即S[k1+1,n]<S[i,n],且LCP(s[k1+1,n],S[i,n])=Height[i-1]-1.

由于S[K1+1,n]<=S[K2,n]<S[i,n]

Height[i-1]-1=min(LCP(S[k1+1,n],S[k2,n]),Height[i])

因此结论成立

求Height

首先让Height[i]继承Height[i-1]-1，然后向后暴力延伸,实际使用令H[i]=Height[sa[i]]

H[i]=LCP(s[sa[i],n],s[sa[i]-1,n)
即H[i]表示排名为i与i-1的串的LCP

因此时间复杂度为O(n)

用处

1.求任意两个位置的LCP

2.H的应用：求本质不同子串
$ans= \sum (n+1-sa[i]\(排名为i的后缀的长度)-H[i])$

按照字典序枚举后缀，统计有多少个新出现的前缀，然后排名i的后缀有n+1-sa[i]个前缀，而其中有H[i]个前缀在前一个后缀中有，因此减去即为新出现的

3.求两个串的最长连续公共子串的长度
这里要将第二个串和第一个串用一个特殊字符链接在一起，然后求排名分别在两边的后缀的height值的最大值