后缀数组学习
代码
/*made in mrd*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define fi first
#define se second
#define lu u<<1
#define ru u<<1|1
#define pb push_back
#define bug1(x) cout<<x<<endl
#define bug2(x,y) cout<<x<<' '<<y<<endl
#define pii pair<int,int>
#define bug3(x,y,z) cout<<x<<' '<<y<<' '<<z<<endl
int n;
char s[N];
int sa[N], x[N], y[N], c[N], rk[N], height[N];
// x 代表第一关键词
//y 代表第二关键词
// c代表每个数值的数目
// rk表示从i开始的后缀排名
// sa表示排名为i的后缀起始下标
// height 代表排名为i的和排名i-1的后缀的最长前缀
int m;
int stk[N];
int ans[N];
int res=0;
void get_sa(){
for(int i=1;i<=n;++i) c[x[i]=s[i]]++;
for(int i=2;i<=m;++i) c[i]+=c[i-1];
for(int i=n;i;i--) sa[c[x[i]]--]=i;
//先进行一次基数排序
for(int k=1;k<=n;k<<=1){
int num=0;
//先按照第二关键字排序，下标从i开始的后缀的第二关键字为从i+k开始的第一关键字
//先将无第二关键字的后缀排先名，此时y[i]表示按照第二关键字排名为i的起始下标
for(int i=n-k+1;i<=n;++i) y[++num]=i;
for(int i=1;i<=n;++i){
if(sa[i]>k) y[++num]=sa[i]-k;
//上一层循环中按照第一关键字的排名的下标已经存在sa数组中
//按从小到大顺序枚举sa数组可保证按照第一关键字从小到大
//所有起始下标超过k才存在第二关键字
//将所有存在第二关键字的后缀存储在y数组中，此时是按i + k的第一关键字，下标要-k
}
//将计数数组清空
for(int i=1;i<=m;++i) c[i]=0;
for(int i=1;i<=n;++i) c[x[i]]++;
for(int i=2;i<=m;++i) c[i]+=c[i-1];
for(int i=n;i;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
//y数组存储的是按照第二关键字从小到大排序后的后缀的起始下标
//i从大到小枚举即可保证按照第一关键字排序后依然是按照第二关键字排序后的相对顺序不变
swap(x,y);
//将所有后缀离散化
x[sa[1]]=1,num=1;
//此时y存储的是从i开始的后缀的第一关键字
for(int i=2;i<=n;++i){
//若当前后缀和排名前一位的后缀第一关键字和第二关键字相同则离散化后的数值相同，否则+1
x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
}
if(num==n) break;
m=num;
}
}
void get_height(){
for(int i=1;i<=n;++i) rk[sa[i]]=i;
for(int i=1,k=0;i<=n;++i){
if(rk[i]==1) continue;
if(k) k--;
int j=sa[rk[i]-1];
while(i+k<=n && j+k<=n && s[i+k]==s[j+k]) k++;
height[rk[i]]=k;
}
}
signed main() {
cin>>n;
cin>>s+1;
m=122;
get_sa();
get_height( );
int top=0;
stk[0]=1;
for(int i=2;i<=n;i++)
{
while(top&&height[stk[top]]>=height[i])
{
res-=(stk[top]-stk[top-1])*height[stk[top]];
top--;
}
res+=(i-stk[top])*height[i],stk[++top]=i;
ans[sa[i]]+=res;
}
res=0;
top=0;
stk[0]=n+1;
for(int i=n;i>=1;--i){
ans[sa[i]]+=res+n-sa[i]+1;
if(i==1) continue;
while(top && height[stk[top]]>=height[i]){
res-=1ll*(stk[top-1]-stk[top])*height[stk[top]];
top--;
}
res+=1ll*(stk[top]-i)*height[i],stk[++top]=i;
}
for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
return 0;
}
/*
* ┌───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
* │Esc│ │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│ ┌┐ ┌┐ ┌┐
* └───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘ └┘ └┘ └┘
* ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
* │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
* ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
* │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | │ │Del│End│PDn│ │ 7 │ 8 │ 9 │ │
* ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
* │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│ '│ Enter │ │ 4 │ 5 │ 6 │ │
* ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤ ┌───┐ ├───┼───┼───┼───┤
* │ Shift │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│ Shift │ │ ↑ │ │ 1 │ 2 │ 3 │ │
* ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* │ Ctrl│ Win│ Alt│ Space │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │ 0 │ . │←─┘│
* └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
*/
练习题
代码同上