后缀数组 学习笔记
定义
我们定义后缀数组 \(Sa\) 中的元素 \(Sa_i\) 为，字典序排名为 \(i\) 的后缀所在的位置。我们定义排名数组 \(Rank\) 中的元素 \(Rank_i\) 为，在位置 \(i\) 的后缀的排名。
求解后缀数组
首先 \(O(n^2logn)\) 的解法很显然，直接排序。
那么有一个利用倍增的思想求解后缀数组的 \(O(nlog^2n)\)的解法 ，首先，我们优先对单个字符排序，发现出现重复的话，我们倍增扩大长度，再次进行比较，直到每个后缀的排名各不相同。
其实还有 \(O(nlogn)\) 和 \(O(n)\) 的解法，详见 后缀数组简介 - OI Wiki
Code
/*
* @Author: Ehundategh
* @Date: 2023-10-22 20:15:56
* @FilePath: \Code\Model\String\SA.cpp
* @Description: You Steal,I kill
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 2000010
using namespace std;
int Suffix_Array[MAXN],Rank[MAXN],n,k,Height[MAXN];
int Temp[MAXN];
char In[MAXN];
bool cmpsa(int i,int j){
if(Rank[i]!=Rank[j]){
return Rank[i]<Rank[j];
}
else{
int Secondi=i+k<=n?Rank[i+k]:-1;
int Secondj=j+k<=n?Rank[j+k]:-1;
return Secondi<Secondj;
}
}
void Get_SA(){
for(int i=1;i<=n;i++){
Suffix_Array[i]=i; Rank[i]=In[i];
}
for(k=1;k<=n;k*=2){
sort(Suffix_Array+1,Suffix_Array+n+1,cmpsa);
Temp[Suffix_Array[1]]=0;
for(int i=1;i<=n;i++){
Temp[Suffix_Array[i+1]]=Temp[Suffix_Array[i]]+(cmpsa(Suffix_Array[i],Suffix_Array[i+1])?1:0);
}
for(int i=1;i<=n;i++) Rank[i]=Temp[i];
}
return;
}
int main(){
scanf("%s",In+1);
n=strlen(In+1);
Get_SA();
for(int i=1;i<=n;i++) printf("%d ",Suffix_Array[i]);
}
这样就可以求出后缀数组了。
例题：
[[JSOI 2007]字符加密]([P4051 JSOI2007] 字符加密 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
思路
首先我们先把字符串复制一遍，那么将全新的字符串的后缀排序，从后缀排名从小到大遍历，如果出现后缀位置在原串中，就输出当前位置前一个位置的字符
高度数组
高度数组，后缀数组的神。
分为以下三个部分讲解：
- 定义
- 求解
- 例题
定义
首先我们先定义 \(LCP(S1,S2)\)(longest Common Prefix) 即最长公共前缀，为：一个最大的 \(x\) 满足 $ S1_i=S2_i (\forall1\le i\le x)$。而我们下面提到的 \(LCP(a,b)\)，都是表示以 \((a,b)\) 两个位置为起点的后缀的最长公共前缀。
我们定义：\(Height_i=LCP(Sa_i,Sa_{i-1})\)，特别地， \(Height_1=0\)。
举个例子，方便理解高度数组。
我们来看以下的字符串：\(\texttt{abcbc}\)，对于这一个字符串，我们尝试求解其高度数组。
首先有 \(Height_1=0\)。
然后我们来求解 \(Height_2\)，将 \(Sa_2\) 与 \(Sa_1\) 作比较求最长公共前缀，也就是求解 \(\texttt{abcbc}\) 和 \(\texttt{bc}\) 的最长公共前缀，也就是 \(0\)。
然后对于 \(Height_3\)，将 \(Sa_3\) 与 \(Sa_2\) 作比较求最长公共前缀，那么比较 \(\texttt{bc}\) 和 \(\texttt{bcbc}\) 即可，答案为 \(2\)。
对于 \(Height_4\) 和 \(Height_5\) 同理可得答案为，\(0,1\)。
求解
求解有一个神奇的引理 \(Height_{Rank_i} \ge Height_{Rank_{i-1}}-1\)。
关于这个引理的证明。详见2009国家队论文。
那么我们就可以通过这个引理，来实现 \(O(n)\) 时间复杂度的高度数组处理。
每次尝试与排名上一个的后缀比较，拓展得到当前的 \(Height_i\) 即可，而拓展也不用从 \(0\) 开始，从上次的 \(Height_i-1\) 开始即可，这样高度数组最多变化 \(3n\) 次，所以时间复杂度是 \(O(n)\)。
代码
void Get_Height(){
for(int i=1,k=0;i<=n;i++){
if(Rank[i]==0)continue;
if(k>0) --k;
while(In[i+k]==In[Suffix_Array[Rank[i]-1]+k])++k;
Height[Rank[i]]=k;
}
}
例题
思路
高度数组模板题，对于每一个字符开头的后缀只需要每次统计总共的子串个数，然后再减去两两后缀的最长公共前缀去重即可。
思路
对于每一组询问，求Height的max即可。（话说这道题有一个加强版，要求出现k次，但是其实是一个做法，只需要求相邻k-1个的Height的max即可）