KMP 和 PAM 的可持久化主要解决一个问题：去均摊分析。

KMP 的可持久化

操作：

  1. 插入字符
  2. 回溯
  3. 问最大周期

希望能维护一个 KMP 形状的可持久化结构。

方法 1

为了去除时间复杂度中的均摊分析部分，类似 AC 自动机一样，如果一个前缀的某个儿子不是其下一个字符，那么记录其的失配（不知道叫不叫这个名字，反正这么个意思）。

所以，将每个节点的儿子数组用可持久化结构维护，同时把 fail 树的结构也给类似的可持久化一下（这个可持久化不是指用可持久化数据结构维护，是指后一个版本的 fail 树可以借用前一个版本 fail 树的一些节点，只要这些节点信息相同）。

所以每次插入字符只需要修改两个节点：一个原来的后缀，一个新增的后缀，同时新的 fail 树除了这两个节点以外的部分都不用动，而且原后缀在 fail 树中没有节点指向他，所以可以直接在新 fail 树上偷梁换柱，以下是一个例子：

![1.png]

时间复杂度：$O(q\log{S})$ 。

但是需要注意，这样子形成的失配结构和 AC 自动机有本质区别，什么意思呢？

如果我们按照回溯的情况，来建出一个 Trie ，然后在这个 Trie 上跑出 AC 自动机，那么这个 AC 自动机的失配和可持久化的失配是不同的。

例如：$ab$ 后回溯，插入 $b$ ，如果 AC 自动机，回溯后 $ab$ 会指向 $b$ ，可持久化不会。

这种做法的本质是在时间 Trie 上维护每个点到根的失配数组，由于不基于均摊，时间复杂度是对的，当然，既然都这样了，也可以不用可持久化的方式维护失配树组，直接开一个数组，时间复杂度是：$O(qS)$ 的。

如果还要维护原串信息，原串也得用可持久化线段树维护一下。

一点变式：

众所周知，字符串的数据结构往往可以在维护的时候往上跳几个 fail ，有时候会有奇效，比如 SAM 时间复杂度的证明就要看 last 的 fail 相关的信息。

而这里也可以，我们可以维护一个新的 $\mathrm{quick[c]}$ 数组，表达的意思是，如果这个节点失配了，那么其最长的前缀满足下一个字符是 $c$ 是哪个节点。

这个的意义在哪呢？它弱化了字符串的存在，认为每个节点都是一个字符串（原字符串的前缀），而 $\mathrm{quick[c]}$ 只由这个节点的字符串决定，而不由总的字符串决定，这有时候会方便思考。

而这种遍历在 KMP 上体现的一般不多，但是在其余数据结构例如 PAM 上体现就比较多了，因为 KMP 上每个节点的字符串和原串前缀一一对应，因此即使只看每个节点的字符串，两者关系也是藕断丝连，但是 PAM 不一样，他是从原串中抽离出所有回文串，因此这个变式就显得很有用了。

方法 2

KMP 的失配有一个很重要的结论：

如果 $x$ 在跳 $fail$ 的时候失败了，而且 $2\mathrm{len[fail[x]]}>\mathrm{len[x]}$ ，那么可以直接跳到 $len[x]\%(len[x]-len[fail[x]])+(len[x]-len[fail[x]])$ ，用这个结论，再用可持久化数据结构维护一下 $fail$ 数组和原串就轻轻松松了。

时间复杂度：$O(q\log^2{n})$ 。

慢了，但是好写得多，而且原串信息也顺便维护了，所以这是 KMP 可持久化的主流写法。

练习

https://www.luogu.com.cn/problem/P5287

PAM 的可持久化

PAM 的去均摊化

PAM 和 KMP 不同的是，每个节点和原串关系，但不多，因为你不能说每个回文串在原串中的前一个字符和后一个字符是啥，回文串是原串中抽象的概念。

但是注意到，现在我们从一个 PAM 上的节点开始匹配，我们只关心两个值：这个串在现在串位置中的前一个字符 $c_1$ 和后一个字符 $c_2$ 。

那我们是不是要维护 $S^2$ 种结果呢？

不然，还是那句话，字符串的数据结构总是可以往 fail 上跳一跳，我们维护在这个节点失配后往上跳的匹配结果，注意到这时上面的回文前后缀一定在这个回文串的里面，所以只要我们知道这个回文串，下面的串所需要的他们的前一个字符我们就已知了。

所以，我们维护 $\mathrm{quick[c]}$ 表示这个节点失配后，后一个字符是 $c$ 的匹配结果，类似 KMP 的，可以 $O(S)$ 数组维护或者 $O(\log{S})$ 可持久化维护。

PAM 的各种扩展

后面添加/删除

直接用去均摊化的 PAM 即可。

注意在每个节点维护这个节点作为最长后缀的次数，归零删除。

Trie 上的 PAM

如果不均摊化，类似 AC 自动机，时间复杂度是所有叶子节点深度和。

均摊化是 size ，原串信息可以在 DFS 时记录。

可持久化 PAM

同样的，只不过需要用可持久化数据结构维护一下原串信息。

练习

Trie PAM ：https://vjudge.net/problem/CodeChef-TREEPAL

1