如题，这篇主要讲字符串题，偏应用，与思维方式

原本是对着NOI大纲上字符串那一栏做的，并自己把SAM和SA强行加进来了，因为我觉得它们也应该在字符串这一栏讲。

这一部分基础知识大多比较简单，很多人都会，所以我们来讨论如何灵活的运用它们。

哈希

这个应该人均会

哈希+思维: NOI2016优秀的拆分

设 (f(i),g(i)) 表示 (i) 位置向前/向后形如 (AA) 的串的数量。那么答案为 (sum f(i) imes g(i+1))

(f,g) 没有本质区别。考虑求 (f)，(g) 反过来做一遍就行。

我们枚举 (A) 的长度为 (i)，然后考虑每隔 (i) 个位置就打一个标记。

然后观察性质发现，任意选一段 (AA) 串，一定会经过恰好两个标记。两标记以前的位置，是一段LCS；两标记以后的位置，是一段LCP。

那我们就枚举相邻两个标记，看 LCP+LCS 是否比 (i) 大就行了。

哈希一波，或者SA一波，就能 (O(log n)/O(1)) 的算 LCP 和 LCS，然后算标记的复杂度是调和级数，就能通过本题。

KMP

KMP，简单吧，超级简单，不用讲了

有时，越是以为简单的东西，越不简单。尤其是一个算法，如果和思维结合起来，就会变的他妈都不认识

KMP+思维: Fibonacci words

我一开始想了好久，想了各种神秘字符串结构，都⑧行

一看题解，竟然只需要KMP

首先对于两个串 (A,B)，在里面匹配 (T)，我们可以在 (A,B)​ 中分别匹配，然后处理一下跨区间的匹配。设 (f_n)

表示 (T) 在串 (F_n) 中的匹配。

那么 (f_n=f_{n-1}+f_{n-2}+I(F_{n-1},F_{n-2})), (I(A,B)) 表示 (T) 跨越 (A,B) 的匹配。

对于这个递推式，前两项我们可以直接加，关键在于后面的那个 (I)。注意到，当 (F_n) 开始比 (T) 长的时候，它中间的很长一段咱都不要了，只保留 长度为 (T)​ 的前后缀就行。每次匹配就暴力跑个 KMP，反正咱已经把串长降下来了。这样复杂度就是 (O(nT)) 的了。

利用fail: CF432D

这是一个经典套路：把KMP的fail数组建成树，称 “失配树”，或者fail树

我们注意到，ACAM，PAM，SAM里面都有fail树的说法。所以这个KMP其实也是个自动机，可以认为是这样：

对于我们的模式串 (T)，

• 点 (x) 表示，当前串能匹配到 (T[:x])
• 节点之间有着一些边：(xxrightarrow[]{T_{x+1}} x+1)​
• 有一种fail边，当字符边不匹配的时候，就走fail边，再看能不能匹配

那这么说把fail树建出来有什么用呢？

有着以下几个性质：（暂时只有一个，等待补充）

• (i) 节点的子树size，就是前缀 (i) 在串中出现的次数

然后就可以解决掉CF432D这个题了

Trie 字典树

trie本身很sb，相信大家都会

利用trie结构解决字典序的限制: USACO2012 First!

先建好fail树，考虑每个串。

如果它要成为最小的那个串，我们就需要手动调整字母表的顺序。

在trie树上看，假设在某一层，当前串的对应位上，字符是 (c)，那这个 (c) 就要比当前节点所有兄弟节点对应的那个字符 (c’) 要 “小”。（带引号的“小”表示，在我们自定义的顺序中的小于）

形式化的说，我们枚举一个串 (s)，然后在trie上走，上一步走到 (u)，当前字符是 (c)，(u) 走 (c) 边走到 (v)，就是当前位置。

那 (forall c’
eq c)， (u) 存在 (c’) 转移，转移到 (v’)，(c) 要“小于” (c’)。

这很显然，对于这些 (v’) 对应的串，设为 (s’) ，和 (s) 的 LCP 显然就是 (u) 对应的那些串，而它俩第一个不同的字符就是 (c) 和 (c’)。我们要让 (s) “小于” (s’)，那么 (c) 就要 “小于” (c’)。

我们这样跑下来，会建立最多 (inom{26}{2}) 个关系。跑一遍拓扑排序，只要不存在环，就是合法的。

复杂度 (O(sum S imes A^2))，(A) 为字符集大小 ，(A=26)。

Suffix Array(SA) 后缀数组

不会的看 这里

注意，SA的复杂度和字符集大小并没有很大关系，就算是一个整数序列也可以跑SA。

SA+并查集: poj1743

SA有一个很常见的trick，就是用并查集把height>=k的位置并起来考虑。

那怎么解决这个题呢？

我们转化一下“相似”这个条件，注意到两个序列如果可以通过整体加某个数得到，那么它俩差分除了第一个位置都相同。

那我们相当于在差分序列上求最长的两个子串，使得它俩相同，并且不相交。

倒着枚举长度 (k)。每次把height=k的两个位置并起来，那每次就相当于height>=k的位置并在一块。

height>=k，就说明有一个长度为 (k) 的子串，在这些位置 全部 都出现过。

然后我们维护一下每一块里的最小、最大位置，看看它俩的差是不是 (>k) 就行了。

其实这个合并的过程，如果一次合并多个叉，就相当于是建后缀树的过程

SA+思维: CF319D

我们可以这样考虑：枚举长度 (i:1…n)，把长度 (=i) 且相邻连续出现两次的串 一块 删掉，复杂度是多少？

看起来好像是 (O(n)) 的。但是，有效删除（删除至少一个位置的操作）次数，其实是 (O(sqrt{n})) 的

注意到 1+2+3… 这个东西是平方级别增长的，要超过 (n) 也只需要 (O(sqrt{n})) 的级别。

那我们怎么算相邻连续出现两次的串呢？

往上翻到NOI2016优秀的拆分，打标记就行。

注意精细实现：只有每次 有效删除 之后重构SA，其它时候就打标记看看有没有解。

复杂度是 (O(nsqrt{n}+nlog n)=O(nsqrt{n}))

树上SA: gym 102511G

我们把串反过来之后，发现，“加前面”变成“加后面”，然后就可以建出一颗trie树来，尽管我们不能直接存下每个串。

然后，“问前缀”也就变成了“问后缀”

那这个咋做呢？

我们发现，还是“问前缀”好做。于是我们考虑，在trie树上，从下到上 还原这些串，并搞出一个结构，支持前缀的查询。

很明显我们不能把每个串都搞出来，也不太方便建一个trie出来。那么什么结构可以支持前缀的查询呢？

SAM！ —— 很明显建不出来

SA！—— 建不出来，吗？

普通的SA是在序列上倍增，我们考虑 在树上倍增，建SA

很好搞，就记一个倍增跳祖先的数组 (jump(u,i))，表示 (u) 的 (2^i) 级祖先。然后把 ((rank(u),rank(jump(u,i)))) 这个 pair 搞一个基数排序就行了。时间复杂度是 (O(nlog n))，(n) 为 trie 上的节点数。

本题的关键在于想出 “树上倍增建SA” 这个事情，想到了之后就迎刃而解了。

Suffix Automaton (SAM) 后缀自动机

不会的看 这里

SAM维护子串的匹配: USACO2010 Threatening Letter

SAM是一个可以接受所有子串的自动机。

那它就可以像KMP一样，维护一个 子串的匹配

如这个题，有一个明显的贪心策略：

设打印好的信件那个串是 (S)，FJ要发的内容是 (T)

每次在 (T) 找到最长的一个前缀使得它是 (S) 的子串，然后划一段，就行了

为啥？很明显，如果我们能划一个串，就能划它任意的子串，因为子串的子串还是子串。那我们让剩下的尽可能少，就是最优的。

把 (S) 建一个 SAM，用 SAM 维护这个匹配就行：每次在自动机上走不动了，就划一段，并回到初始节点