构造

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值是1,复制的新节点dp值是0.
用拓扑排序写起来常数更小,代码复杂度也妙。

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.

习题

练习题:BZOJ#3998 [TJOI2015]弦论

#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");
}

血まみれからの方がさ,勝つ時にはカッコイイだろう.