后缀数组（个人笔记）
柒葉灬
2019-03-22 20:42:42
# 后缀数组SA 总结
------
### 后缀数组就是把长度为n的字符串分成n个后缀
### 并把这n个后缀按字典序排序
### 最后通过一个height数组实现字符串各种应用
------
#### 模板
```cpp
void radix_sort(){
for(int i=0;i<=M;i++)cnt[i]=0;
for(int i=1;i<=n;i++)cnt[Rank[i]]++;
for(int i=1;i<=M;i++)cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--)SA[cnt[Rank[tp[i]]]--]=tp[i];
}
void suffix_sort(){
M=200;
Rank[n+1]=0;
for(int i=1;i<=n;i++){
Rank[i]=str[i];
tp[i]=i;
}
radix_sort();
for(int w=1,p=0;p<n;w<<=1){
p=0;
for(int i=1;i<=w;i++)
tp[++p]=n-w+i;
for(int i=1;i<=n;i++)
if(SA[i]>w)tp[++p]=SA[i]-w;
radix_sort();
memcpy(tp,Rank,sizeof(Rank));
Rank[SA[1]]=p=1;
for(int i=2;i<=n;i++){
Rank[SA[i]]=(tp[SA[i]]==tp[SA[i-1]]&&tp[SA[i]+w]==tp[SA[i-1]+w]?p:++p);
}
M=p;
}
}
void GetHeight(){
int k=0;
for(int i=1;i<=n;i++){
if(k)k--;
int j=SA[Rank[i]-1];
while(i+k<=n&&j+k<=n&&str[i+k]==str[j+k])k++;
height[Rank[i]]=k;
}
}
```
#### 有几个关于后缀数组实现的问题说一下
```cpp
for(int i=2;i<=n;i++){
Rank[SA[i]]=(tp[SA[i]]==tp[SA[i-1]]&&tp[SA[i]+w]==tp[SA[i-1]+w]?p:++p);
}
```
这段代码里面，$SA[i]+w$会不会超过$n$呢？
答案是会的，
例如在字符串$"abab"$当中，
在比较前面的$"ab"$和后面一个$"ab"$的时候
由于相同，会继续比较$SA[i]+w$，
此时就会访问到大于$n$的位置。
#### 那么，会不会访问到很远呢？
答案是不会的，
$SA[i]+w$最多只有$n+1$，原因很简单，
因为如果$SA[i]+w>n+1$的时候，
$tp[SA[i]]==tp[SA[i-1]]$肯定不成立，
因为比较的字符串长度都不一样。
#### 所以说，如果多case，只要Rank[n+1]=0即可。
------
## 后缀数组能解决的经典问题
eg：求两个后缀的最长公共前缀（lcp）。
显然最长公共前缀是二者之间高度数组的最小值。
可以用$ST$表维护。
（网上有O(n)的标准$rmq$算法）
[专题B](https://vjudge.net/contest/284586#problem/B)
#### 题意：求一个最长长度的子串，使得在原串当中出现了$K$次（可以重叠）。
#### 思路：二分长度，然后扫一遍高度数组，判断是否存在这样的子串。
-------
[专题C](https://vjudge.net/contest/284586#problem/C)
#### 题意：求一个串当中有多少个不同的子串。
#### 思路：子串一定是后缀的前缀，所以只要扫一遍高度数组，把重复的前缀减掉即可。
------
[专题D](https://vjudge.net/contest/284586#problem/D)
#### 题意：求一个串当中最长的回文串，如果有多个，输出第一个。
#### 思路：把串倒过来接在原串后面，用一个"#"连接，然后枚举中点（注意长度可以是偶数），求两个串的LCP即可。
-----
[专题F](https://vjudge.net/contest/284586#problem/F)
#### 题意：求最多连续出现的子串，即"ababab"是"ab"出现了3次。
#### 思路：枚举子串的长度K，如果有这种子串，他一定会在{str[1],str[1+k],str[1+2*k]...}中相邻两个出现，然后找他们向前向后分别能最远匹配多远。（注意还要判一下字典序！）
-----
更多的内容可以看国家队论文。
更多的好题目尽在专题里面