构造
SAM的构造是在线插入，详细证明略去，以下只提供插入单个字符代码（笑
int tr[N][33],fa[N],len[N],siz[N],las=1,tot=2;
inline void ins(int x){
ri p=las,q=tot++;las=q;
len[q]=len[p]+1,siz[q]=1;
while(p&&!tr[p][x]) tr[p][x]=q,p=fa[p];
if(p==0) fa[q]=1;
else{
int np=tr[p][x];
if(len[p]+1==len[np]) fa[q]=np;
else{
int nq=tot++;
memcpy(tr[nq],tr[np],sizeof tr[nq]);
fa[nq]=fa[np],fa[np]=fa[q]=nq,len[nq]=len[p]+1;
while(p&&tr[p][x]==np) tr[p][x]=nq,p=fa[p];
}
}
}
拓展
求子串在原串出现次数
其实就是考虑parent树上dp一个点的出现次数，转移是儿子的dp求和，从下往上dp就行，基佬们把它叫做right集合的大小。
注意一个小小区别，插入的新节点初始dp值是
，复制的新节点dp值是
.
用拓扑排序写起来常数更小，代码复杂度也妙。
int cnt[N],sta[N];
inline void tsort(){
ri l=0,r=0;
for(ri i=1;i<tot;i++) cnt[fa[i]]++;
for(ri i=1;i<tot;i++) if(!cnt[i]) sta[r++]=i;
while(l^r){
int t=sta[l++];
siz[fa[t]]+=siz[t];
if(--cnt[fa[t]]==0) sta[r++]=fa[t];
}
}
子串第k大
如果本质相同子串算一个，就建个SAM直接跑dfs，dp出每个点之后会走出多少种子串，贪心求解。
如果本质相同子串按出现次数算个数，就先跑一遍right集合大小，统计出子串出现次数再dp。
以上两种方法dp类似，但初始的dp状态不同。第一种把SAM当作一个普普通通接受子串的自动机，而第二种每个节点上还有一个初始dp值，是每个子串出现的次数。
具体代码见练习题1.
习题
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1000010;
int tr[N][33],fa[N],len[N],siz[N],las=1,tot=2;
inline void ins(int x){
ri p=las,q=tot++;las=q;
len[q]=len[p]+1,siz[q]=1;
while(p&&!tr[p][x]) tr[p][x]=q,p=fa[p];
if(p==0) fa[q]=1;
else{
int np=tr[p][x];
if(len[p]+1==len[np]) fa[q]=np;
else{
int nq=tot++;
memcpy(tr[nq],tr[np],sizeof tr[nq]);
fa[nq]=fa[np],fa[np]=fa[q]=nq,len[nq]=len[p]+1;
while(p&&tr[p][x]==np) tr[p][x]=nq,p=fa[p];
}
}
}
int cnt[N],sta[N],dp[N];
inline void tsort(){
ri l=0,r=0;
for(ri i=1;i<tot;i++) cnt[fa[i]]++;
for(ri i=1;i<tot;i++) if(!cnt[i]) sta[r++]=i;
while(l^r){
int t=sta[l++];
siz[fa[t]]+=siz[t];
if(--cnt[fa[t]]==0) sta[r++]=fa[t];
}
}
int dfs(int x){
if(!x||dp[x])return dp[x];
dp[x]=siz[x];
for(ri i=0;i<26;i++){
if(!tr[x][i]) continue;
dp[x]+=dfs(tr[x][i]);
}
return dp[x];
}
int n,T,k,top,flag;
void solve(int x){
if(x!=1)flag=true;
if((k-=siz[x])<=0)return;
for(ri i=0;i<26&&k>0;i++){
if(!tr[x][i])continue;
if(dfs(tr[x][i])<k)k-=dfs(tr[x][i]);
else putchar(i+'a'),solve(tr[x][i]);
}
}
char s[N];
int main(){
scanf("%s%d%d",s,&T,&k);
n=strlen(s);
for(ri i=0;i<n;i++) ins(s[i]-'a');
if(T) tsort();
else for(ri i=2;i<tot;i++) siz[i]=1;
siz[1]=0, solve(1), flag?0:puts("-1");
}
Comments | NOTHING