更新于 2026/7/9 14:27:37 作者

command_block

-1.前面的话

请配合后缀自动机学习笔记(应用篇)食用。

SAM模板的学习原则 : 理解性默写。

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

0.概(che)论(dan)

首先您要知道自动机是个什么东西,建议先去学习$\bf AC$自动机。

$\color{blue}\text{约定}:$ 在下文中, $n$ 或 $|S|$ 表示字符串长度, $\Sigma$ 表示字符集大小。

蒟蒻的理解:有限自动机$=$一个DAG,边上有字母,每走过一条边就相当于带上这个字母。

$\color{blue}\text{约定}:$ 从源点到某个节点的路径可以形成的所有字符串,称为该节点能够表示的字符串(集合)。

然后,某个自动机所有节点表示的字符串的集合取并,就得到该自动机能表示的字符串集合,这个好理解。

比如说, $\rm Tire$ 就能表示各个字符串的所有前缀。

那么, $\rm SAM$ 能表示某个字符串的所有子串,不多不少,正好是所有子串。

此外,为了分析方便,我们的自动机还要满足 : 任意两点的表示集合不交。

首先,我们证明一个$\color{blue}\text{定理}:$ 假如一个字符串能够被 $\rm SAM$ 表示出来,那么其前缀也能被表示出来。

理解 : 自动机都是一个个字符跳的,如果能跳到这个串,那么也一定经过了所有前缀。

所以我们只要构造一个含有所有后缀的自动机,其就含有所有子串。这可能就是 $\rm SAM$ 的名字来源吧……

根据上面的定理,不难想到一个很暴力的算法 : 把原串的所有后缀加入 $\rm Trie$ ,那么所有后缀的所有前缀$=$所有子串。

但是,这可能需要 $O(n^2)$ 个节点,复杂度不知道差到哪里去了……

后缀自动机必须得是是十分高效的,最好点数和边数都是 $O(n)$ 。

我们先来讲一些理论。

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

1.endpos

$\color{blue}\text{约定}:$ 我们定义一个子串的 $\rm endpos$ ,是它在原串中结束位置的集合。

例 : 原串是 $\texttt{ababcb}$ ,那么 ${\rm endpos}(\texttt{ab})=\{2,4\};\ {\rm endpos}(\texttt{b})=\{2,4,6\};\ {\rm endpos}(\texttt{c})=\{5\}$。

下面会简称 $\rm endpos$ 为 $\rm edp$。

我们很快就能想到把所有的子串按照其 $\rm edp$ 分类,按照套路,这应该是有些性质的。

我们把 $\rm edp$ 相同的一堆子串称为一个类 (子串的集合)。

下面设两个字符串分别为 $s1,s2$ ,且约定 $|s1|\leq |s2|$。

• $\color{blue}\text{引理(1.1)}:$ $s1$ 是 $s2$ 的后缀 $\Longleftrightarrow$ ${\rm edp}(s2)\subseteq {\rm edp}(s1)$

比如上文的 ${\rm edp}(\texttt{ab})=\{2,4\};\ {\rm edp}(\texttt{b})=\{2,4,6\}$ ,其中 $\texttt{b}$ 就是 $\texttt{ab}$ 的后缀。

$\color{blue}\text{证明}:$ 在某个 $s2$ 结尾的地方,也必能找出一个 $s1$ (作为 $s2$ 的后缀),可得 ${\rm edp}(s2)\subseteq {\rm edp}(s1)$ (其实这两句话是一个意思)

• $\color{blue}\text{引理(1.2)}:$ $S1,S2$ 的 ${\rm edp}$ 有交 $\large{\Rightarrow}$ ${\rm edp}(s2)\subseteq {\rm edp}(s1)$ , $s1$ 是 $s2$ 的后缀

$\color{blue}\text{证明}:$

因为 ${\rm edp}$ 有交,那么在某个 $s1$ 结尾的地方, $s2$ 与它同在,可得 $s1$ 是 $s2$ 的后缀,然后由$\color{blue}\text{引理(1.1)}$易证。

那么我们能得到,两个 ${\rm edp}$ 要么没有交,要么互相包含。

• $\color{blue}\text{引理(1.3)}:$ 对于一个类,取出其中长度最大的串,其他的串都是它的后缀,而且长度连续。

(即,如果长度$\max=5$ ,长度$\min=2$ ,那么长度 $2,3,4,5$ 都存在)

$\color{blue}\text{证明}:$ 设长度最长的串是$Smax$,长度最短的是$Smin$。

由$\color{blue}\text{引理(1.2)}$得到,一个类中的字符串之间必有后缀关系,易证其他的串都是 $Smax$ 的后缀。

我们考虑 $Smax$ 长度大于 $Smin$ 的每个后缀 $St$ ,很明显 $Smin$ 是 $St$ 的后缀

由$\color{blue}\text{引理(1.1)}$得到 ${\rm edp}(St)\subseteq {\rm edp}(Smin)$ 且 ${\rm edp}(Smax)\subseteq {\rm edp}(St)$。

又有 ${\rm edp}(Smin)={\rm edp}(Smax)$ 所以 ${\rm edp}(Smin)={\rm edp}(St)={\rm edp}(Smax)$ (夹住了),证毕。

例 : $\texttt{aabaab}$,那么 ${\rm edp}=\{3,6\}$ 的一类中,有 $\texttt{b,ab,aab}$ ,长度是连续的,且其中前者是后者的后缀。

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

2.parent tree

那么我们证明了三个引理之后,会发现一些奇妙的性质。

这三个引理仿佛在暗示一个树结构……

考虑某个类,在这个类长度最长的串 $Smax$ 之前添加一个字符,那么这个新串 $Snew$ 一定不属于这个类。

但是 $Smax$ 是 $Snew$ 的后缀,所以有 ${\rm edp}(Snew)\subseteq {\rm edp}(Smin)$ ,也就是说越添字符, $\rm edp$ 集合越小。(字符越多,对匹配的限制就越紧)

我们可以使用子集关系来建立一颗树,就称作$\rm parent$树。

如图, $\texttt{aababa}$ 的$\rm parent$树。

(注意这个图最右边的 "aabab" 前面应该写$5$ )

其中,每个节点后面表的是该类中最长的串。

加字符操作,可以理解为分裂 ${\rm edp}$ ,创造儿子的操作。

你可能会发现把 $\{1,2,4,6\}$ 分成 $\{2\}\{4,6\}$ 的时候 $\{1\}$ 不见了,是因为 $\{1\}$ 已经在最前面,不能再加字符了。这个细节不必特别注意,后面不会用到。

那么说了半天,到底这棵树和 $\rm SAM$ 有什么关系呢?

回顾一下 $\rm SAM$ 需要满足的性质 :

1.所有的节点能表示的字符串集合求并$=$该字符串的所有子串

2.任意两个节点的表示集合没有交

3.点和边都是 $O(n)$ 级别的

接下来就要揭晓谜底了 :

这颗树的节点和 $\rm SAM$ 的节点意义相同,也就是说这玩意有几个点, $\rm SAM$ 就有几个点,而且点表示的子串集合也是相同的。

我们发现这刚好能满足所有的性质,首先,我们是把所有的子串根据 ${\rm edp}$ 分类产生的树,所以这棵树一定含有所有子串。

其次,每个字串的 ${\rm edp}$ 集合是唯一的,不可能被同时分到两个点里面。

$\color{blue}\text{引理(2.1)}$ $\rm parent$树节点数为 $O(n)$。

$\color{blue}\text{证明}:$ 最坏情况下,不考虑消失,那么每加入一个字符,至少把一个类分成两半。

经过 $n-1$ 次分割则能把原来的 $n$ 个都分散,所以最多有 $2n-1$ 个点。

$\color{blue}\text{引理(2.2)}$ 设 $\min(u),\max(u)$ 为$u$这个节点能表示的字符串的最小和最大长度。

若儿子为 $v$ ,父亲为 $u$ ,那么 $\min(v)=\max(u)+1$

我们构造这颗树的时候,就指出 : 在最长串前面加字符可以使得 ${\rm edp}$ 分裂。

那么分裂后的 $\min(v)$ 当然 $=\max(u)+1$ 啦。

所以你从$\rm parent$树中从上到下拉一条链,你会发现这是个不断在前面加入字符的过程。

所以,儿子的所有字符串长度都大于父亲的。

我们称上面那些绿色节点(包含后缀的节点,称为终止节点)产生的链为终止链。

$\color{blue}\text{引理(2.3)}$ 基于$\rm parent$树的 $\rm SAM$ 边数不超过 $O(n)$

$\color{blue}\text{证明}:$

非常随便的一个证明……有可能是错的。

首先,从源点出发能到达所有的点,这是毋庸置疑的,我们只留下一颗(有向)生成树,其余的边都删掉。

这样,每个点都可达,也就是说每个点中至少有一个串是能够被表示出来的。

然后我们查看每个终止节点,可能有某些后缀是无法被表示出来的,我们的目标就是将所有后缀恢复。

我们在后缀自动机上恢复一条边,那么肯定多了一条能够到达终止节点的路径。

为什么呢? 非终止节点肯定是有出度的,因为子串可以在后面加上若干字符变成后缀。

又因为这是个DAG,不存在转圈圈的情况,一直走下去,肯定不会停在非终止节点处,所以加一条边就相当于多了至少一条到达终止节点的路径。

也即:恢复了一个后缀。

那么一共 $n$ 个后缀,所以最多恢复 $n$ 条边就好了。

至此我们发现,如果能够造出基于$\rm parent$树的 $\rm SAM$ 的话,就是满足要求的。

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

3.SAM的构造

先看节点的结构体:

struct SAM_Node
{int t[26],f,len;}

这里的 t[26] 表示自动机的转移(类似AC自动机), f 描述了$\rm parent$树。

len是每个点能够表示字符串的最大长度(也就是前面的$\max(u)$)。

我们采用增量构造法,每次从后面加入一个字符。

前面我们说过,只要构造一个含有所有后缀的自动机,其就含有所有子串。

我们把目前新产生的所有后缀都加入自动机即可。

观察上面的那个图,你会发现一些标绿色的点,这些点被称为终止节点,因为他们的 $\edp$ 包含 $n$ ,也就是说这些点里面包含后缀。

我们新产生的后缀,无非就是在所有旧后缀(包括空)后面再加上一个新字符罢了,那我们的构造工作肯定是从这些终止节点入手。

我们还是对着代码分析吧:

struct SAM_Node
{int t[26],f,len;}
a[...];
int tn,las;
void add(int c)
{
  int p=las,np=++tn;las=np;
  a[np].len=a[p].len+1;
  for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
  if (!p)a[np].f=1;//case 1
  else {
  	int v=a[p].t[c];
  	if (a[v].len==a[p].len+1)a[np].f=v;//case 2
  	else {
      int nv=++tn;a[nv]=a[v];
      a[nv].len=a[p].len+1;//注意这句话要写在for的前面
      for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
      a[np].f=a[v].f=nv;//case 3
    }
  }
}

P.S 源点是1

首先解释一下 p ,是上一次原串被包含的节点,也就是终止链的末尾。

np 就是我们新建的节点,未来的终止链的末尾。

c 是我们当前要加入的字符。

a[np].len=a[p].len+1;
for(;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;

前面的一句就是总长++,没别的。

这个for的意思就是顺藤摸瓜,顺着终止链找到原来的所有后缀,然后连一条当前字符的边到np ,这样就能够加入新的后缀。

然后那个终止条件p是为了保证不会跳出源点。

如果最后跳到源点都一切顺利,那么 np 的 f 就指向 1(空集) ,因为没有其他的类包含任何一个新后缀。

!a[p].t[c]的意思则正相反:发现已经有某个点包含了我们要加入的一个后缀,那么长度比其小的后缀就都已经存在了。那么我们不能把这个串加入两次,进入case 2.

v表示包含那个新后缀的节点。

a[v].len==a[p].len+1,也就是说这个点没有比新后缀更长的串,那么对其 $\rm edp$ 没有多余的限制。

于是乎我们就直接把 np 的 f 指向 v ,就满足 ${\rm edp}(np)\subseteq {\rm edp}(v)$ 条件。

不然的话,这个点里面最长的串并不是新后缀。

所以这个点的 $\rm edp$ 在最新意义下并不包含 $n$ ,进入最复杂的case 3。

我们考虑把 $v$ 分裂,一部分包含比新后缀更长的串,一部分包含比新后缀短的串与新后缀本身。

复制一个点叫 nv ,强行让 nv 中最长串是那个新后缀,所以有 a[nv].len=a[p].len+1;

然后为了满足没有交这个条件,我们要把新后缀及其后缀从原来的 v 中剔除出去。

如何操作呢,先全部复制 v 到 nv ,

for(;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;

然后我们在刚才停下的终止链(包含的都是旧后缀)上继续跳,然后把本来属于 v 的对应入边都夺过来给 nv ,那么一定能从 v 中剔除新后缀(且满足了长度连续的性质)。

现在 nv 的 $\rm edp$ 包含原来的 v (因为更短,限制更小,集合更大),也包含 $n$。

所以我们需要令 a[v].f=a[np].f=nv;

那么,一个 $\rm SAM$ 就构造完毕了,完结撒花!

仅仅有一个能够表示字符串所有子串的“黑盒” $\rm SAM$ 是远远不够的,我们将在应用中详细介绍其性质。