后缀自动机 学习笔记

学习笔记 SAM

---

Perface

  本文是网上某博文[1]的学习笔记。

Automaton: The Definition

A suffix automaton A for a string s is a minimal finite automaton that recognizes the suffixes of s. This means that A is a directed acyclic graph with an initial node i, a set of terminal nodes, and the arrows between nodes are labeled by letters of s. To test whether w is a suffix of s it is enough to start from the initial node of i and follow the arrows corresponding to the letters of w. If we are able to do this for every letter of w and end up in a terminal node, w is a suffix of s.

  对于一个字符串 $T$ ，我们对它建一个 SAM 。
   SAM 是一个 DAG ， SAM 的每一条边有一个 symbol $c$。
   SAM 有一个起点 $s$ 和若干个终端 $t$。
  对于 $T$ 的每一个子串，我们可以从起点 $s$ 开始，经过若干条边，所有边上的 symbol 串起来，得到该子串。

State of SAM

  给定字符串 $T$ 与 $s$ ，定义 $endpos(T,s)$ 表示出现在 $T$ 中的 $s$ 的结束位置的下标的集合。

  对于两个串 $s_1,s_2$ ，若 $endpos(s_1)=endpos(s_2)$ ，则称 $s_1$ 与 $s_2$ 是 endpos-equivalent 的。

  设 $Substrings(u)$ 表示从 $s$ 出发，走到 $u$ 所得到的所有的子串的集合。对上图观察，发现：

$$\forall s_1,s_2\in Substrings(u)$$ ， $s_1$ 与 $s_2$ 是 endpos-equivalent的。

  所以，根据 $endpos$ 的定义，将 $T$ 的所有substrings进行分类。那么，所有endpos-equivalent的substrings放到一个节点。

  我们考虑任意两个子串 $s_1$ 与 $s_2$ ，它们的 $endpos$ 的关系，从而确定点要如何分类。
  不妨设 $|s_1|<|s_2|$ 。
  当 $s_1$ 是 $s_2$ 的suffix时， $endpos(s_2)\subset endpos(s_1)$ 。反之，当 $endpos(s_2)\subset endpos(s_1)$ 时，则存在一个位置 $P\in endpos(s_2)$ ，所以 $P\in endpos(s_1)$ ，而 $|s_1|<|s_2|$ ，所以 $s_1$ 是 $s_2$ 的prefix。
  当 $s_1$ 不是 $s_2$ 的suffix时，必有 $endpos(s_1)\cap endpos(s_2)=\emptyset$。
  综上，有

$$\left\{\begin{aligned}&endpos(s_2)\subset endpos(s_1)&,s_1是s_2的suffix\\&endpos(s_1)\cap endpos(s_2)=\emptyset&,s_1不是s_2的suffix\end{aligned}\right.$$

  接下来考虑，对于同一个节点$u$，它的两个Substrings $s_1$ 和 $s_2$ 有什么性质。
  为了研究性质，我们先研究特殊化的情况。我们设 $longest(u)$ 为 $Substrings(u)$ 中最长的， $shortest(u)$ 为 $Substrings(u)$ 中最短的。 $maxlen=|longest(u)|$ ， $minlen=|shortest(u)|$。
  由于 $endpos(longest(u))=endpos(shortest(u))$ ，根据之前的结论，有 $shortest(u)$ 是 $longest(u)$ 的suffix。同理，对于任意 $s_i\in Substrings(u)$ ，有 $s_i$ 为 $longest(u)$ 的suffix。

  我们还可以得到一个更好的结论。对于任意 $longest(u)$ 的suffix， $|shortest(u)|<|s_i|<|longest(s_i)|$，必有$s_i\in Substrings(u)$。 这是因为， $endpos(longest(u))\subset endpos(s_i)\subset endpos(shortest(u))$ ，由于 $endpos(shortest(u))=endpos(longest(u))$ ，所以 $endpos(s_i)=endpos(shortest(u))=endpos(longest(u))$ ，根据每个节点的 $endpos$ 相同的定义，得证。
  这也就意味着，一个点存的必然是一段连续的suffix。

State's Suffix Link

  给定 State $u,v$ ，定义 $Link(u)=v$ ，其中$maxlen(v)+1=minlen(u)$ 。

   SAM 会把 $T_i$ 的suffix集合 $["",T_i]$切分成若干个区间，每个区间可以视为一个 State ，通过State's Suffix Link连接。

State's Transitions

   给定一个 State $u$ 和 symbol $c$ ，定义 $trans(u,c)=v$ ，表示从 State $u$ 到 State $v$ 可以通过 symbol $c$ 。

   如果存在 $trans(u,c)=v$, State $v$ 与 State $u$ 有什么关系?
   根据定义，直接有$\left\{s+c\in Substrings(v)~|~s\in Substrings(u)\right\}$

  反向思考。对于一个 State $u$ ，定义它的前驱的集合为 $V_u(u)$ 。则有：

$$\cup_{s\in V_u(u)}\left\{s+c\right\}=Substrings(v)$$
  由于 $endpos$ 相同，所以 $c$ 一定相同。

  由于 $Substrings(u)$ 中的是连续的，所以构成它的也要是连续的。所以$Substrings(i),i\in V_u(u)$一定是连续的。所以通过 State's Suffix Link进行连接。上图就是最好的例子。