实现
void ins(int c){
int np = ++dcnt, p = lst; lst = np;
t[np].len = t[p].len + 1, t[np].eps = 1;
while(p && !t[p].ch[c]) t[p].ch[c] = np, p = t[p].fa;
if(!p) t[np].fa = 1;
else{
int q = t[p].ch[c];
if(t[q].len == t[p].len + 1) t[np].fa = q;
else{
int nq = ++dcnt; t[nq].len = t[p].len + 1;
t[nq].fa = t[q].fa, memcpy(t[nq].ch, t[q].ch, sizeof t[q].ch);
while(p && t[p].ch[c] == q) t[p].ch[c] = nq, p = t[p].fa;
t[q].fa = t[np].fa = nq;
}
}
}
应用
检查字符串是否出现
直接在 SAM 上转移即可。
不同子串个数
SAM 是个 DAG，所以可以在上面 DP。
一般来说，DAG上可能重复转移，很难跑计数 DP 的，但是 SAM 有一个性质是 : 任意两个节点的表示集合没有交。
所以从任何一个节点出发的路径组成的串，都是互不相同的，那么只要统计路径数，不需要考虑重复问题。
SAM 每个节点表示的串没有交集，而且一定表示了所有的串。那么把所有节点表示的串的个数加起来就好了，而每个节点表示的个数，也就是 endpos 的大小，就是 maxlen(u)-maxlen(fa).
线段树合并维护 endpos
SAM 的每个节点的 endpos 集合是所有 fa 为这个节点的节点 endpos 集合的并，于是可以线段树合并得到一个节点的 endpos 集合。
习题
CF1037H Security
![[C#] 逆袭——自制日刷千题的AC自动机攻克HDU OJ](https://www.kunjuke.com/file/css/thumb/3.jpg/280-180.jpg)
