后缀自动机（SAM）

代码模板是y总的模板

构造（可以看看oiwiki）

现在，任务转化为实现给当前字符串添加一个字符 c 的过程。算法流程如下：

令$\textit{last}$ 为添加字符 c 之前，整个字符串对应的状态（一开始我们设 $\textit{last}$，算法的最后一步更新 $\textit{last}$）。
创建一个新的状态 $\textit{np}$，并将 $\operatorname{len}(\textit{np}$) 赋值为 $\operatorname{len}$($\textit{last})+1$，在这时 $\operatorname{fa}(\textit{np}$) 的值还未知。
现在我们按以下流程进行（从状态 $\textit{last}$ 开始）。如果还没有到字符 $c$ 的转移，我们就添加一个到状态 $\textit{np}$ 的转移，遍历后缀链接。如果在某个点已经存在到字符 $c$ 的转移，我们就停下来，并将这个状态标记为 p。
如果没有找到这样的状态 $p$，我们就到达了虚拟状态 $-1$，我们将 $\operatorname{fa}(\textit{np})$ 赋值为 $1$ 并退出。
假设现在我们找到了一个状态 $p$，其可以通过字符 $c$ 转移。我们将转移到的状态标记为 $q$。
现在我们分类讨论两种状态，要么 $\operatorname{len}(p) + 1 = \operatorname{len}(q)$，要么不是。
如果 $\operatorname{len}(p)+1=\operatorname{len}(q)$，我们只要将 $\operatorname{fa}(\textit{np})$ 赋值为 $q$ 并退出。
否则就会有些复杂。需要 复制 状态 $q$：我们创建一个新的状态 $\textit{nq}$，复制$q$的除了 $\operatorname{len}$ 的值以外的所有信息（后缀链接和转移）。我们将 $\operatorname{len}(\textit{nq})$ 赋值为 $\operatorname{len}(p)+1$。
复制之后，我们将后缀链接从 $\textit{np}$ 指向 $\textit{nq}$，也从 $q$ 指向$\textit{nq}$。
最终我们需要使用后缀链接从状态 $p$ 往回走，只要存在一条通过 $p$ 到状态 $q$ 的转移，就将该转移重定向到状态 $\textit{nq}$。
以上三种情况，在完成这个过程之后，我们将 $\textit{last}$ 的值更新为状态 $\textit{np}$。

代码

#include <bits/stdc++.h>

const int N = 2e6 + 10;

int tot = 1, last = 1;
struct Node{
    int len, fa;
    int ch[26];
}node[N];

//构造的过程，配合上面的文字看更容易理解
void extend(int c){
    int p = last, np = last = ++ tot;//创建一个新状态同时更新last的值
    node[np].len = node[p].len + 1;//将len(np) 赋值为 len(p) + 1

    //如果还没有到字符 c的转移，我们就添加一个到状态 np的转移，遍历后缀链接。
    //如果在某个点已经存在到字符 c的转移，我们就停下来，并将这个状态标记为 p
    for(; p && !node[p].ch[c]; p = node[p].fa) node[p].ch[c] = np;
    if(!p) node[np].fa = 1;//如果没有找到这样的状态p,我们就达到了虚拟状态-1, 将link(np) 赋值为1并推出
    else{
        int q = node[p].ch[c];  //如果我们找到了,我们将该状态记为 q;
        //接下来有两种情况: 是否满足 len(q) == len(p) + 1
        if(node[q].len == node[p].len + 1) node[np].fa = q; 如果满足,我们将link(np) 赋值为 q并退出
        else{
            int nq = ++ tot;    //否则克隆一个q点nq,并将其len赋值为len(p) + 1
            node[nq] = node[q], node[nq].len = node[p].len + 1;
            node[np].fa = node[q].fa = nq;//并将link(np) 和 link(q) 都赋值为 nq
            for(; p && node[p].ch[c] == q; p = node[p].fa) node[p].ch[c] = nq; 
            //最终我们需要使用后缀链接从状态 p往回走，只要存在一条通过p到状态q的转移，就将该转移重定向到状态 nq。
        }
    }
}