后缀系列字符串结构总结
博主的一些习惯
字符串叫\(S\)，长度叫\(n\)，字符串\(a,b\)相接为\(a+b\)，下标从一开始，\(S_{i,j}\)表示\(i\)到\(j\)这一段子串
字符串之间\(<,>\)表示字典序比较
所有例题的题解都可以在文末找到
\[ \ \]
\[ \ \]
需要数组\(rk[i]\)表示第\(i\)个后缀的排名(不存在相同)，\(sa[i]\)表示排名为\(i\)的后缀编号，以及辅助数组\(cnt,tmp\)
由于博主水平不够，所以没有去学习dc3(\(O(n)\))算法，下文介绍的是da(\(O(n\log n)\))算法
后缀排序，顾名思义就是要对于\(S\)的每个后缀\(S_{i,n}\)(下称\(Suf_i\))，按照字典序排序，空字符的字典序最小
考虑用倍增+基数排序实现
对于当前已经确定的长度\(k\)，即\(S_{i,i+k-1}\)(超出部分为空字符)的排序已经完成，接下来考虑对于\(S_{i,i+2k-1}\)的排序
\(S_{i,i+2k-1}=S_{i,i+k-1}+S_{i+k,i+2k-1}\)，所以可以根据已经排序完的部分为值对于两部分使用基数排序合并得到\(2k\)
如果你还不是很熟悉这样情况下基数排序的过程，可以先用快排实现一次
流程大致如下
根据首字母初始化sa,rk数组
for(k=1;k<=n;k<<=1) {
rep(i,1,n) tmp[i]=i;
sort(...);
求出sa,rk，注意当前相同的串的rk也要相同
}代码实现
int n;
char s[N];
int cnt[N],tmp[N],rk[N],sa[N],lcp[N];
void PreMake(){
memset(cnt,0,800);
rep(i,1,n) cnt[(int)s[i]]++;
rep(i,1,200) cnt[i]+=cnt[i-1];
rep(i,1,n) rk[i]=cnt[(int)s[i]],sa[i]=i; //瞎初始化一波,不用我这样写
rep(i,n+1,n*2) rk[i]=0;// 注意一下边界的清空
for(reg int k=1;k<=n;k<<=1) {
rep(i,0,n) cnt[i]=0;
rep(i,1,n) cnt[rk[i+k]]++;
rep(i,1,n) cnt[i]+=cnt[i-1];
drep(i,n,1) tmp[cnt[rk[i+k]]--]=i; // 按照第二关键字排序
rep(i,0,n) cnt[i]=0;
rep(i,1,n) cnt[rk[i]]++;
rep(i,1,n) cnt[i]+=cnt[i-1];
drep(i,n,1) sa[cnt[rk[tmp[i]]]--]=tmp[i];//按照第一关键字排序,求出 sa
rep(i,1,n) tmp[sa[i]]=tmp[sa[i-1]]+(rk[sa[i]]!=rk[sa[i-1]]||rk[sa[i]+k]!=rk[sa[i-1]+k]);
rep(i,1,n) rk[i]=tmp[i];//求出rk,注意相同的
}
}
实测贼慢，这个板子应该不行。。。
\[ \ \]
\[ \ \]
SA的另一个重要部分就是\(LCP\)数组（有些地方称之为\(height\)数组，没有关系啦）
\(LCP\): Longest Common Prefix ，最长公共前缀
\(LCP[i]\)：\(LCP(Suf_{sa[i]},Suf_{sa[i+1]})\)
首先对于任意串\(S_1,S_2,S_3\)，有\(LCP(S_1,S_2)\ge min(LCP(S_1,S_3),LCP(S_2,S_3))\)，这个想必不用多说
接下来证明$LCP(Suf_i,Suf_j)>min(LCP(Suf_i,Suf_k),LCP(Suf_k,Suf_j)) $不存在
设\(LCP(Suf_i,Suf_k)=a,LCP(Suf_k,Suf_j)=b\)
若\(a>b\)，有\(S_{j+b} \ne S_{k+b}\)，而因为\(a>b\)可以得到\(S_{k+b}=S_{i+b}\)，即\(S_{i+b}\ne S_{j+b}\)故不存在
若\(b>a\)，同理
若\(a=b\)，则\(S_{i+a}\ne S_{k+a},S_{k+a}\ne S_{j+a}\)，又因为按照字典序排序，所以又有\(S_{i+a}<S_{k+a}<S_{j+a}\)，同样的可以排除上面的情况
得证（额这个自己搞的勉强看看吧）
\[ \ \]
事实上\(LCP[rk[i]]=LCP(Suf_i,Suf_{sa[rk[i]-1]})\)
另\(Suf_i=a,Suf_{sa[rk[i]-1]}=b,Suf_{i+1}=c,Suf_{sa[rk[i+1]-1]}=d,LCP[rk[i]]=x,LCP[rk[i+1]]=y\)
以下仅讨论\(x\ge 2\)的情况，\(x\leq 1\)的情况额。。。
\(c\)串就是\(a\)去掉了首字母，所以有\(a_{1,x}=b_{1,x},a_{2,x}=c_{1,x-1}\)
现在\(d\)的字典序小于\(c\)，若\(d_{1,x-1}\ne c_{1,x-1}\)，则\(d_{1,x-1}<c_{1,x-1}\)
而我们已经知道存在后缀\(e=b_{2,len(b)}\)满足\(e_{1,x-1}=c_{1,x-1}\)由于\(x\ge 2\)，又有\(e<c\)
则\(d<e<c\)矛盾
故\(d_{1,x-1}=c_{1,x-1}\)
根据性质2，可以得到一个\(O(n)\)处理\(LCP\)数组的方法
for(reg int i=1,h=0;i<=n;++i) {
if(h) h--; // LCP[rk[i+1]]>=LCP[rk[i]]
int j=sa[rk[i]-1];
while(i+h<=n && j+h<=n && s[i+h]==s[j+h]) h++;
lcp[rk[i]-1]=h;
}
//由于0<=h<=n,h最多减少n次，所以h最多增加n*2次\[ \ \]
根据性质1，可以转化为求\(min(LCP[rk[i]..rk[j]-1]) (rk[i]\leq rk[j])\)
注意一下边界问题，用 ST表/线段树 维护即可
\[ \ \]
对于排序后的子串\(sa[i]\)，答案就是\(\sum n-sa[i]+1-LCP[i-1]\)
对于\(sa[i]\)这个后缀提供的\(n-sa[i]+1\)个前缀，字典序小于它的串中已经出现过的前缀数量就是最大的\(LCP(Suf_i,Suf_j)\)，也就是\(LCP[i-1]\)
SPOJ-DISUBSTR - Distinct Substrings
\[ \ \]
将两个串接在一起，中间加上一些奇怪的字符
然后就是求下标分别落在两个串中的所有\(i,j\)中\(LCP(Suf_i,Suf_j)\)的最大值
按照\(SA\)的顺序可以发现只用考虑最近的\(i,j\)，所以对于每个 \(i\) 找到最近的 \(j\) 即可，就是一个尺取
\[ \ \]
由于后缀数组已经排好序，所以可对于\(sa[i]\)考虑其贡献的个数为\(n-sa[i]+1-lcp[i-1]\)
考虑个数累前缀和\(Sum[i]\)，二分就\(Sum[p]\ge k\)能得知要找的串在哪个后缀\(p\)的前缀集里，但是这个后缀可能不止出现的一次
求得的长度\(len=k-Sum[p-1]+lcp[p-1]\)就是排名再加上已经出现的
所有包含这个串的后缀是一段连续的区间\(l,r\)满足\(\forall_{i\in [l,r]}LCP(sa[i],p)\ge len\)
可以解决一些问题
\[ \ \]
第一种情况我们可以将\(LCP\)数组分段，每段内的\(LCP[i]\ge x\)，那么出现这些后缀长度为\(x\)的前缀均相同，然后统计每段最多包含几个后缀即可
第二种情况可以直接套一个二分。。。
例题 [USACO06DEC]牛奶模式Milk Patterns
如果要求不能有重复部分的话就要判断一下出现位置的距离 POJ - 1743
类似这样分组还可解决很多问题，如：POJ-3294
\[ \ \]
\(LCP(Suf_i,Suf_j)\ge j-i+1(i\leq j)\)时就出现了循环，可以根据匹配长度来判断循环数
当然还有一些别的方法，原理都类似
例题题解传送门集合：
SPOJ-DISUBSTR - Distinct Substrings
原文：https://www.cnblogs.com/chasedeath/p/12213329.html