字符串进阶算法 1 ：exKMP、SA、SAM、后缀平衡树

exKMP / Z函数

对于字符串 $s$ 的每个后缀，求其与 $s$ 的最长公共前缀 $z_i$

要求 $O(n)$

我们考虑当前在对 $i$ 进行操作。

之前已经有一段区间 $[l,r]$ 满足 $s[1,r-l+1]=s[l, r]$ ，且 $r$ 最大。

对字符串 $s$ 的所有后缀按字典序排序。

要求 $O(n\log n)$

我们考虑先比较所有后缀的第一位，这可以使用桶排 $O(n)$ 。

接下来我们再通过倍增比较前2位、前4位、8位、16位、32位：

用 $O(n)$ 个节点存 $s$ 的所有后缀

对于每个节点，它代表的串是长这样子的：

我们有两棵树：

在线构建。我们考虑加入一个字符 $c$ ，新建一个节点 $u$ ：

连nxt，前面所有段的 nxt[x][c]=u （在 nxt[x][c] 为空时）

寻找前面这些段的过程只需要不断跳fail即可。（即不断右移红色段）
如果现在出现一个 nxt[p][c] = q = != 0，我们就陷入讨论了
- 如果 $len[q]=len[p]+1$ ，即 $q$ 对于 $p$ 来说，只在后面添加字母，没有延长前面的红色段，那么就可以直接 $fail_u=q$
- 否则，我们需要把 $q$ 前面的红色段切成两段。不妨记长的一段是 $q$ ，短的一段是 $cq$ 。那样子和 $p,u$ 产生关联的都是 $cq$ 了（u的fail和p的next）
  
  $q$ 与 $cq$ 的关系则为 $fail_q=cq$

对于SA解决的问题，我们现在要带修（头加头减）

我们考虑建一棵平衡树，维护每个后缀，考虑我们从后往前，从短往长，插入每个后缀，考虑我们在每个节点上与那个节点的字符串 $A$ 比较：

直接逐位比较法：复杂度很大
如果我们当前加入的是 $s[i:n]$ ，而我们已经知道了 $s[i+1:n]$ 的排位了。

所以我们可以先比较第一位 $s[i]$ ，如果相同，我们就用后缀平衡树查询 $s[i+1:n]$ 的排位与 $n$ 比较

复杂度 $O(n\log ^2n)$
我们如果让每个节点对应一个实数区间的话，我们就可以直接比较这个实数区间的大小关系

复杂度 $O(n\log n)$

但这样子可能需要一些不旋转的平衡树，比如替罪羊等。