概念
后缀数组，即对于一个串，它的每个后缀按字典序排序后得到的数组。
有两个数组要求：
- \(SA_i\):排名为 \(i\) 的后缀的开头位置
- \(RK_i\):以 \(i\) 为开头的后缀的排名
朴素
sort排序一下
优化
倍增优化：我们进行 \(\log n\) 次排序，第 \(k\) 次取所有后缀的前 \(2^k\) 个字符进行排序。若上次排序第 \(i\) 为开头的后缀排名为 \(rkl_i\)（可并列），那假如这次需要比较以 \(i\) 开头的串与以 \(j\) 开头的串，只需要先比较 \(rkl_i\) 与 \(rkl_j\)，若相等再比较 \(rkl_i+2^{k-1}\) 与 \(rkl_j+2^{k-1}\) 即可。显然这样是正确的。
#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
string a;
int sa[1000005],rk[1000005],tmp[1000005];
int k;
inline bool cmp(int x,int y)
{
if(rk[x]==rk[y]) //前2^(k-1)相等，比较后k个
{
int i=(x+k<=a.size()?rk[x+k]:-1); //防止越界
int j=(y+k<=a.size()?rk[y+k]:-1);
return i<j;
}
return rk[x]<rk[y];
}
void GetSark()
{
for(int i=0;i<=a.size();i++) //初始化
{
sa[i]=i;
rk[i]=(i<a.size()?a[i]+1:0);
}
for(int i=1;i<=a.size();i=i*2)
{
k=i;
sort(sa,sa+a.size()+1,cmp); //基排懒了
tmp[sa[0]]=0; //暂存rk
for(int z=1;z<=a.size();z++)
{
tmp[sa[z]]=tmp[sa[z-1]]+(cmp(sa[z-1],sa[z])?1:0); //如果比上一个大，排名就增加
}
for(int z=0;z<=a.size();z++)
{
rk[z]=tmp[z]; //复制
}
}
}
signed main()
{
cin>>a;
GetSark();
for(int i=a.size();i>=1;i--) //注意，最后有空串
{
sa[i]++;
rk[i]=rk[i-1];
}
for(int i=1;i<=a.size();i++)
{
cout<<sa[i]<<' '<<rk[i]<<endl;
}
}
应用
在字符串 \(S\) 中找字符串 \(T\)
二分排名即可
bool find(string S,string T)
{
int l=0,r=S.size(),ans;
while(l<=r)
{
int mid=r+l>>1;
if(S.compare(sa[mid],T.size(),T)==-1)
{
l=mid+1;
}
else
{
ans=mid;
r=mid-1;
}
}
return S.compare(sa[ans],T.size(),T)==0;
}
LCP
LCP即最长公共前缀
SA排完序后，有：
- \(lcp(i,j)=\min(lcp(i,k),lcp(k,j))(1 \le i \le k \le j)\)
- \(lcp(i,j)=\min(lcp(k,k-1))(1 \le i < k \le j)\)
height
后缀数组的另一应用
\(height_i\) 表示 \(lcp(sa_i,sa_{i-1})\)，即排名相邻的两个后缀的最长公共前缀的长度。求 \(lcp(i,j)\) 直接RMQ即可。
对于 \(i>1\) 且 \(RK_i>1\)，一定有 \(h_i≥h_{i-1}-1\)
则 \(O(n)\) 扫一扫就可以了
void get_height()
{
int k=0;
for(int i=1;i<=a.size();i++)
{
if(k)
{
k--;
}
int j=sa[rk[i]-1];
while(a[i+k]==a[j+k]) k++;
height[rk[i]]=k;
}
}