先贴一个板子

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+50;
int n,mxlen[N],trans[N][26],link[N],tot=1,lst=1;char s[N];
void extend(int c){
    int cur=++tot,p;
    mxlen[cur]=mxlen[lst]+1;
    for(p=lst;p&&!trans[p][c];p=link[p])trans[p][c]=cur;
    if(!p)link[cur]=1;
    else{
        int q=trans[p][c];
        if(mxlen[q]==mxlen[p]+1)link[cur]=q;
        else{
            int clone=++tot;
            memcpy(trans[clone],trans[q],sizeof(trans[q]));
            link[clone]=link[q];mxlen[clone]=mxlen[p]+1;
            for(;p&&trans[p][c]==q;p=link[p])trans[p][c]=clone;
            link[q]=link[cur]=clone;
        }
    }
    lst=cur;
}

然后是一些性质。

SAM是一个DAG。

从SS节点到自动机上任意一个节点的任意一条合法路径都对应了原串的一个子串。

把节点称为状态,每个子串都仅属于一个状态。

每一个状态包含了它包含的最长子串(长度设为mxlenmxlen)的一些连续长度的后缀。

一个状态p包含的最短子串长度mnlen=mxlen[link[p]]+1mnlen=mxlen[link[p]]+1。

设一个子串ss属于状态pp,那么ss的所有后缀都包含在pp到SS由linklink构成的链上。

对于一个状态所包含的所有子串,它们的endpos()endpos()是相同的,即它们在原串中出现的次数和位置都是相同的。

对于一个状态包含的子串的出现次数(即∣endpos(p)∣\left|endpos(p)\right|)可以通过linklink求出。每次extendextend时新增的curcur的次数为1,然后拓扑排序一下cnt[link[p]]+=cnt[p]cnt[link[p]]+=cnt[p]

SAM的节点数不超过2n−12n-1,因为除了前两次插入外,每一次都有可能再分裂出一个节点。有趣的是，这一上限无法被改善，即存在达到这一上限的例子： abbb...。每次添加都需要分裂。

SAM的边数不超过3n−43n−4,这个不会证233

对于任意两个子串ss和tt,且ss属于状态aa,tt属于状态bb,他们最长公共后缀的长度为min(mxlen[lca(a,b)],∣s∣,∣t∣)min(mxlen[lca(a,b)],|s|,|t|),其中lcalca表示两个节点在linklink构成的树中的lcalca。

要求出子串s[l...r]s[l...r]所在的状态,可以先把pp放到前缀rr所在状态,然后在linklink树上倍增跳到最浅的mxlen>=r−l+1mxlen>=r-l+1的状态。

一个子串ss在串中只出现了1次当且仅当ss所在状态pp在linklink树中是叶子。分pp是否是cloneclone讨论一下易证。突然发现这好像是定义...linklink树上的父亲之所以是父亲就是因为∣endpos()∣|endpos()|变大了...
查询一个串 SS 的子串 [a,b][a,b] 在子串 [c,d][c,d] 中出现次数： [a,b][a,b] 在 [c,d][c,d] 中出现，那么一定会作为 [c,d][c,d] 的一个前缀的后缀。是后缀的话就会在这个前缀代表的状态的祖先链上。于是我们倍增出 [a,b][a,b] 所在状态，然后在下标为前缀标号的线段树中去查 [d−b+a,d][d-b+a,d] 的区间和。线段树合并。
构建SAM的复杂度是O(len∗len*字符集大小)的,还可以用map优化到O(len∗loglen*log字符集大小)

注意对SAM的操作都要等建好了再操作,因为在构建时SAM的结构随时会变化(如linklink)

题目和详细的讲解可以做hihoCoder的后缀自动机专题,讲得真的不错(我这个蒟蒻都能看懂)。

可视化

后缀自动机的问题应该这么考虑：一个串的一个前缀能给它的所有后缀带来什么贡献（即以一个位置为结尾的所有串的贡献）？然后就可以更自然地转化为子树和问题，再去上什么线段树合并。
AC自动机其实也一样：AC自动机是多串匹配，可以处理很多个串分别在另一个串中出现几次的问题。这个也是考虑以每个位置为结尾的所有串的贡献。首先要明确一个前缀走到的一个点的fail链是这个串所有合法的后缀匹配到的点。那么这些节点都是以当前位置为结尾的串，只要对这条链+1，那么就转化为子树和即可。
回文自动机：

void extend(int i){
    int c=s[i],p=lst;
    while(s[i-len[p]-1]!=s[i])p=fail[p];
    if(ch[p][c]){lst=ch[p][c];return;}
    int x=fail[p],y=++cnt;
    while(s[i-len[x]-1]!=s[i])x=fail[x];
    fail[y]=ch[x][c];len[y]=len[p]+2;
    lst=ch[p][c]=y;d[y]=d[fail[y]]+1;
}

这个奇根是 11 偶根是 00 是有讲究的。考虑找fail的时候，对于一个长不为 11 的回文串他一定有合法的回文后缀，而对于长为 11 的回文串，它的fail应该指向偶根。这时我们看到赋值的时候是把 ch[x][c]ch[x][c] 赋给 fail[y]fail[y]。而如果这个回文串长是 11，则这个 xx 是奇根，且它没有 cc 这个儿子，即 ch[x][c]ch[x][c] 是 00。而 00 正好是偶根，就满足fail指向偶根了。
它的fail链也是对于一个串所有后缀回文串，也是用上面的思想处理问题。
然后提一句复杂度分析。对于这两个while，我们考虑每执行一次while，是在fail树上向上爬，而每插入一个新节点只会在fail树上向下走一步。于是是 O(n)O(n) 的。