后缀数组
cpp
struct SuffixArray{
int n;
vector<int> sa,rk,lc;
SuffixArray(const string &s){
n=s.length();
sa.resize(n);//sa[i]为排名为第i位的后缀
rk.resize(n);//rk[i]为第i位后缀的排名
lc.resize(n);//lc为排名第i位与i-1位的最长公共前缀
//lcp(i,i)=len(i),lcp(i,j)=min(lcp(i,k),lcp(k,j))
iota(sa.begin(),sa.end(),0);
sort(sa.begin(),sa.end(),[&](int a,int b){return s[a]<s[b];});
//先按照每一位排
rk[sa[0]]=0;
for(int i=1;i<n;i++){
rk[sa[i]]=rk[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]);
}
int k=1;
vector<int> tmp,cnt(n);//tmp用来存取第二关键字排序，cnt用于第一关键字的基数排序
while(rk[sa[n-1]]<n-1){
tmp.clear();
//后面k个数，第二关键字必定为空，排前面
for(int i=0;i<k;i++){
tmp.push_back(n-k+i);
}
//剩下n-k个数，第二关键字必定为之前排序的第一关键字的顺序
for(auto i:sa){
if(i>=k)tmp.push_back(i-k);
}
fill(cnt.begin(),cnt.end(),0);
for(int i=0;i<n;i++)cnt[rk[i]]++;
for(int i=1;i<n;i++)cnt[i]+=cnt[i-1];
for(int i=n-1;i>=0;i--)sa[--cnt[rk[tmp[i]]]]=tmp[i];
swap(rk,tmp);
rk[sa[0]]=0;
for(int i=1;i<n;i++){
rk[sa[i]]=rk[sa[i-1]]+(tmp[sa[i-1]]<tmp[sa[i]]||sa[i-1]+k==n||tmp[sa[i-1]+k]<tmp[sa[i]+k]);
/*
1. 都有第二关键字，如果第一关键字相等，会在第三次判断，否则在第一次判断
2. 都没有第二关键字，在第一次判断
3. 前面没有，后面有，第二次判断
*/
}
k*=2;
}
//对于第i个后缀和第i-1个后缀，有lc[rk[i]]>=lc[rk[i-1]]-1
//k最多加2*n次，得到线性做法
for(int i=0,k=0;i<n;i++){
if(rk[i]==0)continue;
if(k)k--;
int j=sa[rk[i]-1];
while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
lc[rk[i]]=k;
}
}
};