后缀数组
模板
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;
}
}
};P2178 [NOI2015] 品酒大会
题意：
给定一个长度为n的字符串，n杯酒，美味度为a[i]，如果str(p,p+r-1)=str(q,q+r-1)，则称p和q是r相似的，二者的总美味度为两个数的乘积
对于每个r从0到n-1，求出最大美味度
思路：
- 假设p和q后缀的最长公共前缀为lcp，则p和q为0~lcp相似的
- 则对于排名后的后缀，假设当前要找r相似，那么如果一个
lc[i]<r，那么会将数组分成[1,i-1]和[i,n]两部分 - 同理，如果有多个，则会分成多条线段，这些线段内部的酒是r相似的
- r越大，分开的段落越多，因此考虑r从大到小算，则每次将一些线段合并成一部分即可
- 用并查集实现合并操作，维护最大次大和最小次小值
cpp
struct SuffixArray{
int n;
vector<int> sa,rk,lc;
SuffixArray(){}
SuffixArray(const string &s){
n=s.length();
sa.resize(n);
rk.resize(n);
lc.resize(n);
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);
while(rk[sa[n-1]]<n-1){
tmp.clear();
for(int i=0;i<k;i++)tmp.push_back(n-k+i);
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]);
}
k*=2;
}
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;
}
}
};
int tot=0,maxv=-INF;
struct DSU{
vector<int> par,siz,mx1,mx2,mn1,mn2;
DSU(){}
DSU(int n){
par.resize(n);
siz.resize(n,1);
mx1.resize(n);
mx2.resize(n);
mn1.resize(n);
mn2.resize(n);
iota(par.begin(),par.end(),0);
}
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
bool merge(int x,int y){
x=find(x),y=find(y);
tot-=get(siz[x])+get(siz[y]);
siz[y]+=siz[x];
par[x]=y;
tot+=get(siz[y]);
if(mx1[x]>=mx1[y])mx2[y]=max(mx1[y],mx2[x]),mx1[y]=mx1[x];
else mx2[y]=max(mx2[y],mx1[x]);
if(mn1[x]<=mn1[y])mn2[y]=min(mn1[y],mn2[x]),mn1[y]=mn1[x];
else mn2[y]=min(mn2[y],mn1[x]);
maxv=max(maxv,max(mx1[y]*mx2[y],mn1[y]*mn2[y]));
return true;
}
int get(int x){
return x*(x-1)/2;
}
};
DSU dsu;
SuffixArray suf;
vector<int> hs[N];
PII cal(int r){
for(auto x:hs[r]){
dsu.merge(x-1,x);
}
if(maxv==-INF)return {tot,0};
return {tot,maxv};
}
void solve(){
int n;
string s;
cin>>n>>s;
suf=SuffixArray(s);
vector<int> a(n);
dsu=DSU(n);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=1;i<n;i++)hs[suf.lc[i]].push_back(i);
for(int i=0;i<n;i++){
dsu.mx1[i]=dsu.mn1[i]=a[suf.sa[i]];
dsu.mx2[i]=-INF,dsu.mn2[i]=INF;
}
vector<PII> ans;
for(int i=n-1;i>=0;i--){
ans.push_back(cal(i));
}
reverse(ans.begin(),ans.end());
for(auto [x,y]:ans)cout<<x<<" "<<y<<"\n";
}P4070 [SDOI2016] 生成魔咒
题意：
n次操作，初始为空串，每次往后面加一个字符，然后计算总的子串个数
思路：
- 将整个字符串翻转，倒着做，相当于删除最前面的字符，即删除一个后缀
- 对于一个后缀而言，它多产生的不相同的子串，为后缀长度-lcp
- 使用双链表维护前面一个后缀和后面后缀即可
cpp
struct SuffixArray{
int n;
vector<int> sa,rk,lc;
SuffixArray(){}
SuffixArray(vector<int>&s){
n=s.size();
sa.resize(n);
rk.resize(n);
lc.resize(n);
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);
while(rk[sa[n-1]]<n-1){
tmp.clear();
for(int i=0;i<k;i++)tmp.push_back(n-k+i);
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]);
}
k*=2;
}
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;
}
}
};
int get(int x){
static map<int,int> mp;
static int num=0;
if(!mp.count(x))mp[x]=num++;
return mp[x];
}
void solve(){
vector<int> s;
int n;
cin>>n;
for(int i=0;i<n;i++){
int c;
cin>>c;
s.push_back(get(c));
}
vector<int> ans(n);
reverse(s.begin(),s.end());
SuffixArray suf(s);
vector<int> u(n+10),d(n+10);//双链表
int res=0;
for(int i=0;i<n;i++){
res+=n-suf.sa[i]-suf.lc[i];
u[i]=i==0?n+2:i-1;
d[i]=i+1;
}
d[n+1]=0,u[n]=n-1;
for(int i=0;i<n;i++){
ans[i]=res;
int k=suf.rk[i],j=d[k];
res-=n-suf.sa[k]-suf.lc[k];
if(j<n){
res-=n-suf.sa[j]-suf.lc[j];
suf.lc[j]=min(suf.lc[j],suf.lc[k]);
res+=n-suf.sa[j]-suf.lc[j];
}
d[u[k]]=d[k],u[d[k]]=u[k];
}
for(int i=n-1;i>=0;i--)cout<<ans[i]<<"\n";
}