姬姬复唧唧，后缀自动机

这篇文章写出来就是给自己mark的，我也不指望我自己能讲的多么清楚，毕竟我啥都不会呢

PS: 完全参照 Yonda 的博客

构造后缀自动机

后缀自动机

对于给定的字符串 $S$ 的后缀自动机是一个最小化确定有限状态自动机，用于接受字符串 $S$ 的所有后缀

定义 $endpos$

要找证明和理论知识请戳进这位大佬的博客

每个结点连向它最长的 ($endpos$) 不在该节点的后缀，即长度为 $len(v) = minlen(u) - 1$ 的结点

显然，每个结点的 $Suffix\ Link$ 所连接的结点一定满足 $len(to) < len(now)$， 满足一个以 $t_0$ 为根的树形结构

Yonda 教你构造

通过一个一个添加字符来构造自动机，每次 $extend$ 步骤如下：

  1. $last$ 为当前已添加的整个文本串的对应结点，我们添加字符 $c$

  2. 创建一个新的结点，赋值 $len(now) = len(last) + 1$

  3. 寻找结点 $now$ 的 $Suffix\ Link$ ,此时我们位于结点 $last$, 很明显的，我们要构造出一些路径，使得当前已有的所有后缀，都能通过这些路径形成最新的后缀，于是我们从 $last$ 开始，对于通过每个结点的 $Suffix\ Link$ 而形成的一个树链，我们将所有没有转移$c$的结点，加上一条通过 $c$ 到 $now$ 的转移，并且将第一个有转移$c$的结点记为 $p$ ，并停止，如果走到了 $Link(t_0)$ 都一直没有找到转移$c$，我们将 $Link(now)$ 赋值为 $0$

  4. 对于我们找到的结点 $p$ , 记录 $p$ 通过转移$c$ 到达的结点为 $q$

  5. 如果 $len(p) + 1 = len(q)$ , 说明 $p,q$ 为串中相邻的两个字符，直接使 $Link(now) = q$

  6. 否则，克隆结点 $q$ , 令克隆出的结点为 $clone$ 使得 $len(clone) = len(p) + 1$ , 并复制除了 $len$ 以外的所有数据 , 最后 , 令 $Link(q) = Link(now) = clone$

  7. 从 $p$ 开始，将$Suffix\ Link$ 链上所有的通过转移$c$连向 $q$ 的结点连向 $clone$

  8. 使 $last = now$ ， 下一个

代码
struct state {
    bool isclone;
    int len, link, firstpos;
    map<char, int> next;
    vector<int> invlink;
} st[maxn << 1]; //最坏情况下 2 * strlen(s) 的空间

int sz, last;

void SAM_init() {
    sz = last = 0;
    st[0].len = 0;
    st[0].link = -1;
}

void extend(char c) {
    int now = ++sz;
    st[now].len = st[last].len + 1;
    st[now].firstpos = st[now].len;
    int p, q, clone;
    for(p = last;p != -1 && !st[p].next.count(c); p = st[p].link)
        st[p].next[c] = now;
    if(p == -1) {st[now].link = 0; return ;}
    q = st[p].next[c];
    if(st[p].len + 1 == st[q].len) {
        st[now].link = q; return ;
    }
    clone = ++sz;
    st[clone] = st[q]; st[clone].isclone = 1;
    st[clone].len = st[p].len + 1;
    for(;p != -1 && st[p].next[c] == q; p = st[p].link) {
        st[p].next[c] = clone;
    }
    st[q].link = clone; st[now].link = clone;
    last = now;
}