后缀数组
定义
suf[i] i到最后的子串
rank[i] suf[i]在所有后缀中的排名
sa[i] 排名为 i 的后缀的开始位置
sa[i] 与 rank[i] 为互逆操作,相反的排列
height[i] suf[sa[i]] 与 suf[sa[i-1]] 的最长公共前缀
H[i] 即 Height[rank[i]]
求SA的倍增算法
用基数排序,排序次数为 \(\lceil log n \rceil\)
for(int i=1;i<=n;++i)buc[s[i]]++;
for(int i='a';i<='z';++i)buc[i] += buc[i-1];
for(int i=n;i>=1;--i)sa[buc[s[i]]--] = i;
for(int i=1;i<=n;++i)rk[sa[i]]=rk[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]];)//rank初始化,相同的串相同的rk
for(int k=1;k<=n;k<<=1){//取到 log n , k 代表 1<<(k+1) 的倍增
for(int i=1;i<=n;++i)buc[rk[sa[i]]] = i;
for(int i=n;i>=1;--i)if(sa[i]>k)SA[buc[rk[sa[i]-k]]--]=sa[i]-k;//对rk进行基数排序
for(int i=n-k+1;i<=n;++i)SA[buc[rk[i]]--] = i;
for(int i=1;i<=n;++i)RK[SA[i]]=RK[SA[i-1]]+!cmp(rk,SA[i],SA[i-1],k);
swap(rk,RK);swap(sa,SA);
if(rk[sa[n]]>=n)break;
}
求 height
\(H[i] \geq H[i-1]-1\)
故遍历字符串,基于 H[i-1] 来求解 H[i] 复杂度 O(n)
求两后缀的最长公共前缀(LCP)
是他们排名间的 height 的最小值,因为 sa 按字典序排序,所以最小的height后面不会有另外的字符可以构成公共前缀。
维护 height 数组上的RMQ,如st表,线段树
可重叠的重复最长字串
求两后缀的最长公共前缀,那么就是Height中的最大值
不可重叠的重复最长子串
二分答案
在height中分组,每组后缀的最大height不小于k,看里面sa的极差是否超过k,有一组即合法
标签:suf,前缀,后缀,height,--,数组,sa From: https://www.cnblogs.com/life-of-a-libertine/p/17993316