小太阳的无敌后缀自动姬学习笔记

Posted by WildCow on October 23, 2018

写在前面



“Unbelievable ” —— HighSun




开始



2018.09.17
自动机
  • 有限状态自动机的功能是识别字符串。

    令一个自动机 $A$ ,若它能识别字符串 $s$ ,则记 $A(s)=true$ ,否则记 $A(s)=false$

  • 自动机由五个部分组成:

    • $alpha$ :字符集
    • $state$ :状态集合
    • $init$ :初始状态
    • $end$ :结束状态集合
    • $trans$ :状态转移函数
  • $null$ 表示不存在的状态

  • 令 $trans(s, ch)$ 表示当前状态为 $s$ ,读入字符 $ch$ 后所达到的状态。

    若 $trans(s, ch)$ 不存在,为了方便,设其为 $null$ ,同时有 $null$ 只能转移到 $null$ 。

  • 令$trans(s, str)$ 表示当前状态为 $s$ ,读入字符串 $str$ 后所达到的状态。

那么自动机 $A$ 能识别的字符串就是所有使得 $trans(init, x) \subset end$ 的字符串 $x$ ,令该字符串集合为 $reg(A)$

从状态 $s$ 开始的能识别的字符串,即为所有使得 $trans(s, x) \subset end$ 的字符串 $x$ ,令该字符串集合为 $reg(s)$

后缀自动机的定义 & 相关证明
  • 后缀自动机

    给定字符串 $s$,$s$ 的后缀自动机,简记为 $SAM$ 。是一个能识别所有 $s$ 的后缀的自动机。即 $SAM(x)=true$ ,当且仅当 $x$ 是 $s$ 的后缀。 后缀自动机也能用来识别 $s$ 的所有子串。

    • 字符串 $aabbabd$ 的后缀自动机的最简((蠢))实现:

    字符串 aabbabd 后缀自动机的最简实现

    aabbabd

    ​ 即把字符串的所有后缀插入到一棵 $Trie$ ,时间/空间复杂度 $O(n^2)$ (which is utterly useless)

  • 最简状态后缀自动机

    即状态数最少的后缀自动机 (状态数为线性,证明见下) 。

    假设已经得到了这样一个最简状态后缀自动机 $SAM$ ,令 $ST(str)$ 表示状态 $trans(init, str)$

    有如下分析:

    ​ 令母串为 $S$ ,其后缀集合为 $suf$ ,连续子串集合为 $fac$

    ​ 从位置 $a$ 开始的后缀为 $suffix(a)$

    $S[l,r)$ 表示 $S$ 中 $[l,r)$ 区间所构成的子串,下标从 $0$ 开始 、

    • 对于一个字符串 $s$ ,若其不属于 $fac$ ,则 $ST(s)=null$ ,因为 $s$ 后面添加任何字符串都不可能形成 $S$ 的后缀

      对于一个字符串 $s$ ,若其属于 $fac$ ,则 $ST(s) \neq null$ ,因为此时可以在 $s$ 后面添加一些字符串而形成 $S$ 的后缀

    • 显然不能对每一个 $s \in fac$ 都新建状态 因为 $fac$ 大小为 $O(n^2)$

      对字符串 $a$ ,考虑 $ST(a)$ 能识别哪些字符串,即 $reg(ST(a))$

      字符串 $x$ 能被自动机识别,当且仅当 $x \in suf$ ;那么字符串 $ax$ 能被自动机识别,当且仅当 $ax \in suf$ .

      即 $ax$ 是 $S$ 的后缀, $x$ 也是 $S$ 的后缀, $reg(ST(a))$ 是一些后缀的集合

      **对于一个状态 $s$ ,我们只关心 $reg(s)$ **

    • 如果字符串 $a$ 在母串 $S$ 中的 $[l,r)$ 位置出现,那么 $ST(a)$ 就能识别 $S$ 从位置 $r$ 开始的后缀。

      如果字符串 $a$ 在母串 $S$ 中出现的位置集合为 ${[l_1,r_1), [l_2,r_2),…,[l_n,r_n)}$ ,那么 $reg(ST(a))$ 就是 ${suffix(r_1),suffix(r_2),…,suffix(r_n)}$ ,不妨令 $right(a)={r_1,r_2,…,r_n}$ ,那么 $reg(ST(a))$ 就完全由 $right(a)$ 决定。

    • 考虑两个子串 $a, b \in fac$ ,如果 $right(a) == right(b)$ ,那么有 $ST(a) == ST(b)$ ,于是可知,某一个状态 $s$ 是由所有 $right$ 集合满足 $right(x) = right(s)$ 的字符串 $x$ 组成

      对于一个 $r \in right(s)$ ,只要再确定字串的长度 $len$ ,就可以确定子串了,该子串为 $S[r-len, r]$

    • 考虑对于一个 $right$ 集合,易证:如果长度 $l, r$ 合适,可以确定某子串,那么满足长度 $l \leq m \leq r$ 的 $m$ 也一定合适。即合适长度必然是一个区间

      令 $s$ 对应的合适长度的区间为 $[min(s), max(s)]$

  • 状态数为线性的证明

    • 考虑两个状态 $a,b$ ,它们的 $right$ 集合分别为 $R_a, R_b$ .

      现假设 $R_a, R_b$ 有交集,不妨设 $r \in R_a \cap R_b$ ,考虑这个 $r$ ,那么由于 $a$ 和 $b$ 表示的子串不会有交集$^{[1]}$,所以 $[min(a),max(a)]$ 与 $[min(b),max(b)]$ 也不会有交集。

      不妨令 $max(a)<min(b)$ ,那么 $a$ 中所有子串的长度都小于 $b$ 中的子串长度。又由于它们所表示的字串的结束位置都在 $r$ ,那么 $a$ 中所有串都是 $b$ 中所有串的后缀。因此 $a$ 中某串出现的位置,在 $b$ 中该串也一定出现了。所以 $R_a \subset R_b$ ,即 $R_a$ 是 $R_b$ 的真子集$^{[2]}$

      那么任意两个串的 $right$ 集合,要么不相交,要么一个是另一个的真子集。 (这里是对的)

    • right 集合的树形结构

      right 集合的树形结构 (parent树)

      如上图每个节点代表一个状态,节点上的数字即为该状态的 $right$ 集合。称这棵树为 $parent$ 树。

      这棵树中共有 $n$ 个叶子节点,同时每个内部节点至少有 $2$ 个孩子,容易证明$^{[3]}$树的大小必然是 $O(n)$ 的。

      对一个状态 $s$ ,令 $fa$ 为上图中 $s$ 的父节点,那么显然有 $right(s) \subset right(fa)$ ,并且 $right(fa)$ 是 $right(s)$ 的所有真超集中大小最小的 (即 $fa$ 显然是 $s$ 向上恰好一层时的节点) ,记为 $parent(s)$ .

      考虑长度,状态 $s$ 对应的长度范围是 $[min(s), max(s)]$ 。那么对于长度 $len = min(s)-1$ ,它不在状态 $s$ 对应长度区间内的原因,应当是对于这一长度短了 $1$ 后缀,它在超出状态 $s$ 对应的 $right(s)$ 的某一位置 $r’$ 出现过。并观察到:随着长度的变小,出现的位置将越来越多,那么对于以上提到的长度 $len = min(s) - 1$ ,它必然属于状态 $parent(s)$ 对应的长度范围内。

      那么对状态 $s$ 及其父节点 $fa$ ,有 $max(fa)=min(s)-1$ .

2018.09.18

​ 以上证明了后缀自动机的状态数 (节点数) 是线性的,要证明后缀自动机是一个线性大小的结构,还须证明边数也是线性的。

  • 边数为线性的证明

    首先,如果 $trans(a,ch)==null​$ ( $a​$ 为状态, $ch​$ 为字符) ,这条边就不需要保留。我们要储存的只有有用的边。

    如果有 $trans(a,ch)=b$ ,就看成有一条从状态 $a$ 出发,标号为 $ch$ 的边到状态 $b$ .

    首先对如下 $SAM$ 求出一颗生成树,根为 $init$ :

    SAM的生成树

    字符串 aabbabd 的 SAM

    令状态数为 $M$ ,则生成树中有 $M-1$ 条边。接下来考虑非树边。

    对于一条由状态 $a$ 指向状态 $b$ 的标号为 $c$ 的非树边,我们在后缀自动机上构造一条路径,该路径从 $init$ 沿生成树走到状态 $a$ ,然后从状态 $a$ 走过当前考虑的非树边到状态 $b$ ,再从状态 $b$ 沿任意边到任意一个 $end$ 状态。

    那么这条构造出的路径必然对应一个母串的后缀 ,因为这条路径是由后缀自动机的 $init$ 开始到 $end$ 结束 。一个非树边可以对应多个后缀。现对母串的每一个后缀,在后缀自动机上找到其对应的唯一路径,并建立一个映射,将这一后缀映射到其对应路径的第一条非树边上。

    于是每个后缀将映射到至多一条非树边上;而每个非树边由至少一个后缀映射而来。

    显然$^{[4]}$ ,边的数量也不会超过 $O(n)$ .

一些性质
  • 由于每个子串必然包含在后缀自动机的某个状态里,母串的每个子串都是母串某一后缀的前缀),那么一个字符串 $s$ 是 $S$ 的子串,当且仅当 .

    • 子串判定问题, $ST(s) \neq null$ 则 $s$ 是 $S$ 的子串
    • 子串出现次数:状态 $ST(s)$ 的 $right$ 集合的大小
  • 在一个状态中直接保存其 $right$ 集合将消耗过多的空间,观察上面的 $parent$ 树发现,每个状态的 $right$ 集合就是其在树中所有孩子的 $right$ 集合的并集。进一步就是其下所有叶子节点的 $right$ 集合的并集,因为叶子节点的 $right$ 集合中只有一个元素

    考虑对 $parent$ 树做 $dfs$ 序,则某一状态的 $right$ 集合即为它在 $dfs$ 序中所辖区间内的叶子节点的 $right$ 集合的并集,可以据此快速求$^{[5]}$某一子串的所有出现位置。

定义&性质总结
  • 状态 $s$ ,转移 $trans()$ ,初始状态 $init$ ,结束状态集合 $end$

  • 母串 $S$ ,母串 $S$ 的后缀自动机 $SAM$

  • $right(str)$ 表示 $str$ 在母串 $S$ 中所有出现的结束位置的集合

  • 一个状态 $s$ 表示的所有子串的 $right$ 集合相同,为 $right(s)$

  • 对于一个状态 $s$ , $parent(s)$ 表示这样一个状态 $x$ ,它满足

    • $right(s)$ 是 $right(x)$ 的真子集
    • $right(x)$ 是所有满足上述条件的最小的集合
  • $parent$ 函数因而可以表示为一个树形结构,不妨称为 $parent$ 树

  • 一个 $right$ 集合和一个长度 $len$ 确定了一个 $S$ 的子串

  • 对于状态 $s$ ,使得 $right(s)$ 合法的子串长度是一个区间,记为 $[min(s),max(s)]$

  • $max(parent(s))=min(s)-1$

  • 一个 $SAM$ 的状态数和边数都是 $O(n)$ 的

  • 对状态 $s$ 和字符 $ch$ , $trans(s,ch)=null$ 表示从状态 $s$ 出发没有标号为 $ch$ 的边

  • 考虑两个状态 $s$ 和 $t$ ,对状态 $s$ 有 $right(s)={r_1,r_2,…,r_n}$ ,现假设从状态 $s$ 出发有一条标号为 $ch$ 的边**指向状态 $t$ **。那么考虑状态 $t$ 的 $right$ 集合,由于加了一个字符 $ch$ ,则在 $right(s)$ 中,只有使得 $S[r_i]==ch$ 的 $r_i$ 符合要求$^{[6]}$,于是得 $right(t)={r_i+1|S[r_i]==ch}$

  • 在 $parent$ 树上,若有从状态 $s$ 出发的标号为 $x$ 的边,那么必然有从 $parent(s)$ 出发的标号为 $x$ 的边

    同时,对于状态 $fa=parent(s)$ ,有 $right(trans(s,ch)) \subset right(trans(fa,ch))$

    “有一个很显然的推论是 $max(t)>max(s)$ ” (? 啥)

$O(n)$ 构造

clj:说了这么多,如果不能给出一个构造SAM的算法,也没有意义。

从左到右依次添加 $S$ 中的字符,每次添加一个字符,更新当前的 $SAM$ 使得它成为包含这个新字符的 $SAM$ .

每个阶段
  • 令当前字符串为 $T$ ,新字符为 $x$ ,记 $T$ 的长度为 $L$ ,上述操作即为 $SAM(T) -> SAM(Tx)$ ,每次新增加的子串都是串 $Tx$ 的后缀,而$Tx$ 的后缀,就是在 $T$ 的后缀后加上字符 $x$ 。

    那么考虑所有表示 $T$ 的后缀, 即 $right$ 集合中包含 $L$ 的节点 $v_1,v_2,…,v_k$ ,

    由于必然有且仅有一个满足 $right(p)={L}$ 的节点 $p$ ,那么上述所有 $v_i$ 节点由于 $right$ 集合都包含 $L$ ,那么它们在 $parent$ 树中必然都是节点 $p$ 的祖先,可以用 $parent$ 函数得到它们。

    同时,添加一个字符 $x$ 后,令状态 $np$ 表示 $ST(Tx)$ ,则有 $right(np)={L+1}$

    • 不妨让这些 $v_i$ 从后代到祖先排序: $v_1, v_2, …, v_k$ ,其中 $v_1=p,v_k=root$
  • 考虑其中一个 $v$ 的 $right$ 集合 ${r_1,r_2,…,r_n=L}$ ,那么在它的后面添加一个新字符 $x$ ,形成新的状态 $nv$ 的话,只有使得 $S[r_i]==x$ 的那些 $r_i$ 是符合要求的。

2018.09.19
  • 在之前我们知道,如果不看 $r_n$,若从某状态 $v_i$ 出发没有标号为 $x$ 的边 ,那么该状态 $v_i$ 就没有满足这一要求的 $r_i$ . 并且由于 $v_1, v_2, …$ 的 $right$ 集合是不断扩大的,那么如果从某状态 $v_i$ 出发有标号为 $x$ 的边,那么从状态 $v_{i+1}$ 出发也必有标号为 $x$ 的边。

    现在对于所有没有标号为 $x$ 的状态 $v$ ,它的 $right$ 集合内只有 $r_n=L$ 是满足要求的,那么我们让它连一条到 $np$ 的标号为 $x$ 的边

  • 下面令 $v_p$ 为 $v_1,v_2,…,v_k$ 中第一个有标号为 $x$ 的边的状态。

    考虑 $v_p$ 的 $right$ 集合 ${r_1,r_2,…,r_n=L}$ ,并令 $q=trans(v_p,x)$

    那么 $q$ 的 $right$ 集合就是 ${r_i+1|S[r_i]==x}$ ,注意这是更新前的情况,所以 $r_n$ ,即 $L$ 是不算的

    并且注意:此处不一定能直接向 $q$ 的 $right$ 集合中插入 $L+1$ $^{[7]}$ ,因为可能导致 $max(q)$ 变小,而引发一系列问题。

    当然,如果 $max(q)==max(v_p)+1$ ,则不会有这个问题,这时可以直接向 $right(q)$ 中插入 $L+1$ ,并让 $parent(np)=q$ ,即可结束这一阶段。

2018.09.20
  • 若 $max(q) \neq max(v_p)+1$ ,则不能直接向 $q$ 的 $right$ 集合中插入 $L+1$ 。

    这个时候我们注意到 $q​$ 实际上被分成了两份$^{[8]}​$

    我们新建一个节点 $nq$ ,使 $right(nq)=right(q)\cup{L+1}$ 。这样有 $max(nq)=max(v_p)+1$ ,其中长度加的 $1$ 就是新插入的字符 $x$ 提供的长度

    同时又有 $right(q)​$ 是 $right(nq)​$ 的真子集,那么 $parent(q)=nq​$

    同时 $parent(np)=nq$ ,此处 $np$ 即为上面定义的 $ST(Tx)$

    并且容易证明$^{[9]}$ $parent(nq)=parent(q)$ ,此处 $q$ 为原来的状态 $q$ ,即插入字符 $x$ 前的 $trans(v_p,x)$

2018.09.25

复习了上面的东西好多才刚看懂

2018.09.26

又看了一遍改正了一些自己的手误虽然有的地方还是觉得是clj手误了

下次就往后学快学完了!

2018.09.29
  • 接下来考虑节点 $nq$ ,由于转移过程中的 $L+1$ 是不起作用的,那么对于节点 $nq$ 的 $trans()$ ,就是和原来的 $trans(q)$ 是一样的,拷贝即可。

回忆:

  • $v_1,v_2,…,v_k$ 是所有 $right$ 集合中包含 ${L}$ 的节点按照在 $parent$ 树上从后带到祖先的排序,其中节点 $v_p$ 是其中第一个有标号为 $x$ 的边的节点, $x$ 是这次新加入的字符。
  • $q=trans(v_p,x)$
  • 由于节点 $v_p,…,v_k$ 都有标号为 $x$ 的边,并且到达的点的 $right$ 集合,随着出发点的 $right$ 集合的变大也会变大,那么只有一段 $v_p,…,v_e$ ,通过它们的标号为 $x$ 的边,原先是到达节点 $q$ 的。
  • 那么由于这里 $q$ 节点已经被替换成了 $nq$ ,于是我们只需把 $v_p,…,v_e$ 的 $trans(*, x)$ 设置为 $nq$ 即可。
总结

  • 令当前串为 $T$ ,加入的字符为 $x$
  • 令 $p = ST(T)$ ,那么有 $right(p)={length(T)}$
  • 新建节点 $np=ST(Tx)$ ,那么有 $right(np)={length(T)+1}$
  • 对节点 $p$ 的, 即,$parent$ 树上的所有没有标号为 $x$ 的边的祖先 $v$ ,令 $trans(v,x)=np$
  • 找到节点 $p$ 的第一个有标号为 $x$ 的边的祖先 $v_p$
    • 如果没有这样的 $v_p$ ,令 $parent(p)=root$ ,结束该阶段
  • 令 $q=trans(v_p,x)$
    • 若有 $max(q)=max(v_p)+1$ ,令 $parent(np)=q$ ,结束该阶段
  • 新建节点 $nq$ ,令 $trans(nq,*)=trans(q,*)$ ,并有 $parent$ 树上的关系:
    • $parent(nq)=parent(q)$
    • $parent(q)=nq$
    • $parent(np)=nq$
  • 遍历 $p$ 的祖先中所有的满足 $trans(v,x)$ 的节点,令 $trans(v,x)=nq$ .


注~1~

证明: 用反证法, $a$ 和 $b$ 是当前所考虑的最简状态自动机中的两个不同状态,假设状态 $a$ 与状态 $b$ 表示的子串有交集,设交集中某一子串为 $x$ ,则有 $ST(x) = a$ ,同时又有 $ST(x)=b$ ,推出 $a=b$ ,显然错误。

则 $a$ 与 $b$ 表示的子串不会有交集。

注~2~

WTF,他说反了吧,如果 $a$ 是 $b$ 的子串,那么应该是 $R_b \subset R_a$ 才对啊

Re-edit:正确应当是 $R_b \subset R_a$ . 即长度越小的串,其 $right$ 集合应越大

注~3~ 

证明:树有 $n​$ 个叶子节点,而每个内部节点至少有 $2​$ 个子节点,那么最坏 (使树的节点数最多) 情况下,每个内部节点都有 $2​$ 个子节点,这时树最底层全为叶子节点,共 $n​$ 个,向上一层的节点个数为 $log_2(n)​$ 个,向上两层的节点个数为 $log_2(log_2(n))​$ 个,…,树根节点数为1。

​ 则最终树上的节点个数最多为 $n + log_2(n) + log_2(log_2(n)) + … + 1$ ,即树的大小为 $O(n)$ 。

注~4~

显然。

注~5~

在 $parent$ 树上的所有节点表示的 $right$ 集合之间的关系仅有两种包含不相交,于是每次令新建的节点 $np$ 的right集合大小为 $1$ ,构造完 $SAM$ 后从 $root$ 做一次 $dfs$ 即可,每个节点的 $right$ 集合大小即为其所辖所有子节点的集合大小之和 $+1$ 。

或者直接根据状态 $s$ 的最长长度 $max(s)$ 从大到小排序 ((基数排序 / 计数排序)) 即为 $parent$ 树的拓扑序,然后做一次 $O(n)$ 遍历即可求出所有状态的 $right$ 集合大小。

注~6~

这个 $r_i$ 和一个长度 $len \in [min(s),max(s)]$ 所确定的子串为 $S[r_i-len,r_i)$

即 $r_i$ 不在子串内,子串最后一个字符为 $S[r_i-1]$

注~7~

若在 $right(q)$ 中强行插入 $L+1$ ,会导致 $max(q)$ 变小。

第一行加粗 $v_p$ 结束位置上的长度为 $max(v_p)$ 的串,第二行加粗 $q$ 结束位置上的长度为 $max(q)$ 的串:

​ AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx

AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx

可以看出如果只是简单的在 $right(q)$ 中插入 $L+1$ ,将会造成 $max(q)$ 变小

而如果 $max(q)==max(v_p)-1$ ,则不会有这个问题,这时可以直接插入 $L+1$ ,让 $parent(np)=q$ ,即可结束这一阶段

注~8~
  • $v_p$ 结束位置上的长度为 $max(v_p)$ 的串:

    AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx

  • $q$ 被分成的两份:

    AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx

    AAAAAAxAAAAAAAAAAAAAAxAAAAAAAABAAAAAx

    这两份以子串长度作为区分

注~9~

在之前说到如果有 $max(q)==max(v_p)+1$ 则直接令 $parent(np)=q$ 即可,而此时的状态 $nq$ 是这样一个状态,它是串 $Tx$ 的后缀,且最长长度为 $max(v_p)+1$ ,则在 $parent$ 树上令 $parent(np)=nq$ 即可。

完了





代码



#define maxn 200010         ///两倍字符串长度
#define sigma 26            ///字符集大小
struct SuffixAutomaton{
    int root;               ///root = 0;
    int size, last;
    int go[maxn][sigma];    ///转移
    int maxlen[maxn];       ///节点i代表的子串的最长长度
    int par[maxn];          ///parent树中节点i的父节点
    int cnt[maxn];          ///节点i的right集合大小
    int who[maxn];          ///who[i]是按照maxlen从小到大排序后的第i个节点下标
    int a[maxn];            ///辅助拓扑排序的数组(计数排序)
    SuffixAutomaton():
        size(0){}

    int new_node(int len){
        memset(go[size], -1, sizeof(go[size]));
        maxlen[size] = len;
        par[size] = -1;
        return size ++;
    }
    int idx(char ch){
        return ch - 'a';
    }
    void extend(int ch){
        //printf("extending: %c\n", 'a' + ch);
        int p, q, np, nq;
        p = last;
        np = new_node(maxlen[p] + 1);
        while(p != -1 && go[p][ch] == -1){///在所有的last的祖先中,为所有没有标号为x的边的节点添加一条边指向节点np=ST(Tx)
            go[p][ch] = np;
            p = par[p];
        }
        if(p == -1){///如果last的所有祖先没有标号为x的边,则状态np=trans(Tx)的parent为root
            //printf("par[%d] = root\n", np);
            par[np] = root;
        }
        else {///找到第一个有标号为x的边的状态p,令q=trans(p,x)
            q = go[p][ch];
            if(maxlen[p] + 1 == maxlen[q]){///如果maxlen[p] + 1 == maxlen[q]则直接令q的parent为np
                par[np] = q;
            }
            else {///否则新建节点nq,令maxlen[nq] = maxlen[p] + 1
                nq = new_node(maxlen[p] + 1);
                memcpy(go[nq], go[q], sizeof(go[q]));///nq的状态转移函数与q的完全相同
                par[nq] = par[q];
                par[q] = nq;        ///将parent树上的关系由q->par[q] 修改为 q->nq->par[q]
                par[np] = nq;       ///np=ST(Tx)的parent也是nq
                while(p != -1 && go[p][ch] == q){
                    go[p][ch] = nq;
                    p = par[p];
                }
            }
        }
        last = np;
        cnt[np] = 1;
        //printf("cnt[%d] = %d\n", np, cnt[np]);
    }
    void count(){///拓扑排序并计数每个节点表示的子串出现次数
        memset(a, 0, sizeof(a));
        for(int i = 0; i < size; ++ i)a[maxlen[i]] ++;
        for(int i = 1; i < size; ++ i)a[i] += a[i-1];
        for(int i = size - 1; i >= 0; -- i)who[--a[maxlen[i]]] = i; ///计数排序
        for(int i = size - 1; i >= 0; -- i){
            if(par[who[i]] != -1){
                cnt[par[who[i]]] += cnt[who[i]];
            }
        }
    }
    void init(char *s){
        size = 0;
        last = root = new_node(0);
        memset(cnt, 0, sizeof(cnt));
        int len = strlen(s);
        for(int i = 0; i < len; ++ i){
            extend(idx(s[i]));
        }
        count();
    }
}sam;
#undef sigma
#undef maxn




后文



“我加份代码” —— Zgy