在学完 SAM 后的三周，某场CF的E题，结果忘了 SAM 的写法…

---

本文忽略了复杂度证明，在 OI wiki 上证明的很详细了，这里为对 SAM 的原理的介绍。

SAM 对一个字符串(或多个)的所有子串进行高度压缩，使得 SAM 可以在时间复杂度$O(n)$，空间复杂度$O(n)$被构造出来。确切的说，一个 SAM 最多有 $2n-1$个节点，$3n-4$个边。

初识

一个字符串 $s$ 的后缀自动机是一个接受所有后缀的最小有限状态自动机。

• SAM 是一张 DAG(有向无环图)，节点称作状态，边称为转移，带有一些字母(取决于字符集)，一个节点的所有转移均不相同。

• 存在一个初始状态和若干个结束状态，从初始状态沿着转移到某个结束状态，转移上的字符拼接起来构成字符串某个子串。

例如，对于字符串"abcab"构建的SAM如下，$1$为起始节点(右图为parent tree)：

定义

在构造 SAM 前，先引入几个重要的定义。

结束位置 endpos

字符串 $s$ 的非空子串 $t$ 的 $\operatorname{endpos}(t) $为 $t$ 在 $s$ 中所有出现的位置(以 $0$ 开始计)。

例如对于字符串"abcabbc"，$\operatorname{endpos}("bc")=2,6$

若两个子串的 $\operatorname{endpos}$ 相等，则称这两个子串为同一个 等价类 。也就是说，一个字符串有若干个等价类。SAM 的状态个数取决于等价类的个数，每一个状态对应若干个等价类。

根据等价类的定义有以下引理：

• 引理1：字符串 $s$ 的两个非空子串 $a$,$b$ ($|a|\leq|b|$)为同一个等价类当且仅当 $a$ 的每次出现都以 $b$ 的后缀形式出现。

• 引理2：字符串 $s$ 的两个非空子串 $a$,$b$ ($|a|\leq|b|$)。若 $a$ 是 $b$ 的后缀，则$\operatorname{endpos}(b) \subseteq \operatorname{endpos}(a)$，否则$\operatorname{endpos}(a) \cap \operatorname{endpos}(b)=\varnothing$

• 引理3：一个等价类的所有字符串按照长度从小到大排序，长度恰好覆盖一个区间 $[x,y]$，实际上这个区间就是最短串长度到最长串长度。

引理3证明

设最大串为 $a$ , 最小串为 $b$ , 考虑所有 $a$ 的长度大于 $|b|$ 的后缀，都属于同一个等价类，因为对于一个后缀 $x$ , $b$ 的每次出现都以 $x$ 的后缀出现($|x|>|b|$)，根据引理一：$x$,$b$,$a$,属于同一个等价类。

后缀连接link

以下设起始状态为空串，其$\operatorname{endpos}=\{-1,0,...,|s|-1\}$

SAM 每个非起始状态都对应一个等价类，记最长串为 $a$ , 对于 $a$ 的所有后缀，找出最长的且和 $a$ 不是同一个等价类的后缀，该节点的后缀连接连接到该后缀的 $\operatorname{endpos}$ 对应的节点(也就是该后缀属于的等价类的节点)。

• 引理4：所有后缀连接构成一棵根为起始状态的树

每个状态一定连接到严格更短的子串，向上走一定能到达起始状态。这棵树也成为parent tree。

构造

构造 SAM 为在线算法，每次以加入一个字符$c$构建。

在线性构造 SAM 前，每个状态定义$\operatorname{len}$为最长串的长度，$\operatorname{minlen}$为最短串的长度，根据后缀连接的定义：

$\operatorname{minlen(v)}=\operatorname{link(len(v))}+1$

现在开始构造 SAM ,我们设起始状态为 $st$ , $\operatorname{link}(st)=-1,\operatorname{len}(st)=0$

定义一个辅助状态指针 $last$ 为当前字符串构建时对应的状态，初始 $last=0$

现在加入一个字符 $c$ ，会执行以下流程：

1. 创建一个新的状态 $cur$,令$\operatorname{len}(cur)=\operatorname{len}(last)+1$
2. 从$last$开始，若$last$没有向$c$的转移，则添加，并且跳后缀连接；若找到转移，则停止，记当前状态为$p$。
3. 若第2步跳到了起始状态$st$，即跳到$-1$，则令$\operatorname{link}(cur)=0$ 跳至第7步。
4. 令 $p$ 向 $c$ 的转移的状态为 $q$，分情况讨论：若$\operatorname{len}(q)=\operatorname{len}(p)+1$，则执行第5步，否则跳至第6步。
5. 令$\operatorname{link}(cur)=q$ ，跳至第7步。
6. 复制状态 $q$：新建一个状态 $clone$，
   将 $q$ 除了 $\operatorname{len}$ 的信息复制给 $clone$ , $\operatorname{len}(clone)=\operatorname{len}(p)+1$，令$\operatorname{link}(cur)=clone,\operatorname{link}(q)=clone$，接着从状态 $p$ 开始跳后缀连接，将所有指向 $q$ 的转移改为指向 $clone$。
7. 令 $last=cur$，构建结束。

将整个字符串构建完成后，从最终状态开始($last$)，跳后缀连接，所有非 $st$ 的状态都为终止状态，从$st$到任意终止状态构成的子串一定为原字符串的后缀。

这里对第3,4,5,6步进行进一步解释：

第3步中，状态 $p$ 存在到 $c$ 的转移，为避免转移冲突(避免更改已有的转移)，故不再跳后缀连接。

第4步中，我们有了转移 $(p,q)$，设$p$状态对应的字符串为$x$，则该自动机中就添加了字符串$x+c$。
如何确定$\operatorname{link}(cur)$的指向是问题，按照定义，指向的字符串应该是$x+c$，且长度为$\operatorname{len}(p)+1$，若$q$满足$\operatorname{len}(q)=\operatorname{len}(p)+1$，则$\operatorname{link}(cur)=q$；否则，转移不连续，就需要将$q$拆开，拆出一个$\operatorname{len}=\operatorname{len}(p)+1$的部分，记为$clone$，$\operatorname{link}(cur)=clone$。比如构建"edfbcbc"的SAM，在构建最后一个"c"的时候，会跳到第一个"c"，但我们显然不能把这个"c"和"edfbc"放到同一个状态($\operatorname{endpos}$不同)，所以要复制出来一个。
最后需要重定向到$q$的转移，设状态$p$的最长字符串的所有后缀为$w$，对$w+c$重定向转移即可，所以跳parent tree直到起始节点。
如果不理解的话，可以模拟对"abbb"构建SAM的过程，这里给出结果图：

参考代码

//结构体封装，将a-z转换为0-25转移
void insert(int c)
{
    int p=tot++;
    t[p].len=t[las].len+1;
    int now=las;
    while(now!=-1&&!t[now].ver[c])
    {
        t[now].ver[c]=p;
        now=t[now].link;
    }
    if(now==-1) t[p].link=0;
    else
    {
        int q=t[now].ver[c];
        if(t[now].len+1==t[q].len) t[p].link=q;
        else
        {
            int clone=tot++;
            t[clone].len=t[now].len+1;
            t[clone].link=t[q].link;
            for(int i=0;i<=25;i++) t[clone].ver[i]=t[q].ver[i];
            while(now!=-1&&t[now].ver[c]==q)
            {
                t[now].ver[c]=clone;
                now=t[now].link;
            }
            t[q].link=t[p].link=clone;
        }
    }
    las=p;
}

应用

• 寻找子串

直接在 SAM 上从初始状态跑转移即可。

• 子串个数

本质不同：每个状态对应一个等价类，根据引理，每个状态的所有串长度恰好覆盖区间一个区间，所以状态 $p$ 的本质不同子串个数为：

$\operatorname{maxlen}(p)-\operatorname{minlen}(p)+1=\operatorname{maxlen}(p)-(\operatorname{maxlen}(\operatorname{link}(p))+1)+1=\operatorname{maxlen}(p)-\operatorname{maxlen}(\operatorname{link}(p))$

根据同样的推理方法可以推出不同子串的总长度。

仅位置不同：先计算每个状态的本质不同的子串个数，该状态仅位置不同的个数即为：本质不同子串个数$\times \operatorname{endpos}$大小。

如何求$\operatorname{endpos}$大小？把目光放到parent tree上，该状态的子树的所有状态的$\operatorname{endpos}$都代表该状态$\operatorname{endpos}$的子集，根据 SAM 的性质，该状态的子状态的大小即为其$\operatorname{endpos}$大小，进行一次 dfs 即可。

例题：[模板]后缀自动机 (SAM),[TJOI2015]弦论

• 最早出现位置

文本串 $t$ 对于模式串 $s$ 的早出现位置，需要先找到 $t$ 在 $s$ 中的状态位置，其最早出现位置即为最小 $\operatorname{endpos}$ 。在加入点$p$时最小 $\operatorname{endpos}=\operatorname{len}(p)-1$，在复制点$q$时，最小$\operatorname{endpos}$为$q$的最小出现位置。

同理所有出现位置即为子树的所有最早出现位置。

• 两个串的最长公共子串

设为 $s$ , $t$

后文介绍的 广义SAM 会提及，这里介绍 普通SAM 的解决方法：

对 $s$ 构建 SAM ，遍历 $t$ 的所有前缀，在 $s$ 上找与 $t$ 匹配的最长后缀，具体的：

设$p=t,l=0$，每次添加一个新得字符$c$：

存在$p$到$c$的转移，则转移，$l$自增

若不存在，就要跳后缀连接，直到回到初始状态或找到转移，若回到初始状态，就重设$p=t,l=0$重新开始。

广义SAM

顾名思义就是对多个字符串构建一个SAM

先说明几种假的做法

1. 多个串合并成一个串构建

正确性没问题，但复杂度危险。

2. 构建完一个串后将 $last$ 归 $0$ 重新构建下一个串

正确性是假的。

为什么假了

考虑单串SAM情形，添加一个字符$c$的时候，$last$一定没有向$c$的出边，但在广义SAM上，$last$可能会出现$c$的出边，如果这个转移是不连续的( $\operatorname{len}(q)> \operatorname{len}(p)+1$)，程序会复制一个节点，这时候会发现最初新建的$cur$是个多余的节点，$clone$有它所有的属性，于是$cur$变成了一个空节点！

空节点的产生对于极少数情况计算$siz$，基排都产生了影响，所以就假了，只不过大多数题不会卡掉这种情况。

离线构造

正确的方法是将多个串压入一棵trie树，从低层向高层dfs/bfs建立 SAM ,这里只需要将$last$设置成根到当前trie节点的父亲构成的前缀串在 SAM 的状态编号。

注意,DFS在多模式串插入的复杂度为$O(\sum|S|)$，但在直接给一棵trie的情况下复杂度为$O(|T|^2)$，回溯造成了过多冗杂操作。而BFS时间复杂度不变。

在线构造

根据前文提到的假做法，需要加入特判：

• $last$存在向$c$的出边且转移连续，不需要构建直接返回，若转移不连续，则直接复制转移节点并退出而不再新建节点$cur$。

代码

int insert(int c,int las)
{
    if(ver(las,c))
    {
        int now=las,q=ver(las,c);
        if(len(now)+1==len(q)) return q;
        else
        {
            int clone=++tot; len(clone)=len(now)+1;
            for(int i=0;i<=25;i++) ver(clone,i)=ver(q,i);
            link(clone)=link(q);
            while(now!=-1&&ver(now,c)==q) 
            {
                ver(now,c)=clone;
                now=link(now);
            }
            link(q)=clone;
            return clone;
        }
    }
    //此处为标准SAM构建......  
    //最后返回新建节点cur  
}

应用

• 多个串最长公共子串

每个状态新建一个$cnt_{i,j}$数组，表示状态$i$被字符串$s_j$经过了$cnt_{i,j}$次，在新建节点的时候更新$cnt$，最后跑一遍$dfs$，按照$\operatorname{len}$从大到小的顺序将该节点$cnt$加到$\operatorname{link}$上去，最后随便拿出一个字符串，像两个串最长公共子串一样，跑转移即可，转移可行的条件为对于所有的$k$(字符串数量),$cnt_{p,k}>0$。

带区间限制的一些问题

有些题目要求给定一个文本串$s$和多组模式串$t$，要求只使用$s$的一个子串和模式串进行匹配。

基于这类问题的解法，需要先讨论全局匹配的情况(即没有区间限制)，进而得到带区间限制的情况。

此类问题一般对$s$建立SAM，我们对parent tree跑一遍 dfn序，在dfn序上跑线段树解决。

CF1037H Security

待更,如果忘了的话，就忘了吧(提醒一下)。