字符串学习笔记

· · 个人记录

一切字符串算法的本质都是有效利用失配信息进行匹配或查询！

一、Manacher算法

最长回文子串。暴力是枚举中间点然后左右依次查询，Manacher算法通过之前查询过的中间点来更新后面的。

首先，因为回文串有长度奇偶的区别，所以通过在两两字符之间加 '#' 来化为同种问题。

设之前查到的中间点中匹配的最靠后的为 id，这个最靠后的位置为 mx。设每个点为中心点的最长回文子串长度为 l_i，则：

若 i<mx，那么我们可以通过 i 关于 id 对称的镜像点来给 i 赋值，即

l_i=\min(mx-i,l_{id\times2-i})

取 \min 的原因是只能判断在 id 已经配完的内部可以，外边不一定可以。

否则，则 l_i=1。

这样赋完初值之后再向外拓展可以最终得到 O(n) 复杂度求解最长回文子串。

模板题 AC代码

二、最小表示法

判断两个字符串（可旋转）是否相等。暴力是取出所有可能得到的串，取最小串，看看是否相等。这启发我们可以利用失配信息求最小串：

字符串 s：i 指针；字符串 t：j 指针；两个字符串目前已经匹配的长度设为 k。

若 s_{i+k}=t_{j+k}，则直接 ++k。

若 s_{i+k}>t_{j+k}，那么 i...i+k 这些都一定不是最小串的开头，直接把 i 改为 i+k+1。另一种同理。

模板题中要求一个串的轮换同构串中字典序最小的，直接以此串中两个不同开头的位置做最小表示法，即可最终求得最小串。注意此时两个指针一定不能相等，要特判。

模板题 AC代码

三、KMP字符串匹配

匹配两个字符串，暴力就是两个指针 i,j，从头开始匹配，如果不成功再从头开始，这样复杂度 O(nm)。

如何利用失配信息？首先我们想，当 s_i\neq t_j 的时候，如果我们固定 i 单调不减，那么 j 应该减少的越少越好，因为 j 减少的越少，相当于此时已经匹配的字符数就越多。这启发我们可以先预处理一部分信息，然后每次失配之后 j 都跳到这样一个位置上继续匹配。

仔细思考一下这个位置需要满足什么性质。显然，如果设这个位置为 k，那么相当于要找到一个最大的 k 使其满足 t_{1...k}=t_{j-k+1...j}。

首先假设我们对于每个 i 都找到了上述这样一个位置 nxt_i，那么就可以使用一开始说的方法来计算。注意到我们的匹配次数此时是线性的，复杂度O(m)。

考虑如何预处理。可以发现，预处理实际上就是自己匹配自己的过程，两个指针均指向同一字符串，首先定义 nxt_1=0，接下来通过同样的方式做即可，每个位置的 nxt 值就是当 i 停留在这个位置时最终的 j 值。

模板题 AC代码

四、AC自动机

AC自动机就是在Trie树上对多个子串跑KMP。先建立一个Trie树，然后再Trie树上通过BFS建立fail(相当于KMP中next指针)，匹配的具体流程基本等同于KMP。另外，如果一个单词走到了最后一个字母，那么不管是否匹配成功都应该回到它的fail指针。

模板题 AC代码

五、扩展 KMP

扩展 KMP 可以求出一个子串 T 对一个子串 S 的每一个后缀的最长公共前缀。这个算法之所以被称为 exKMP，是因为其与 KMP 有一些共同特性。

设 extend[i] 表示 T 与 S[i...n] 的最长公共前缀的长度。假设此时我们已经匹配完了 extend[1...i-1]，此时正在匹配 i。设之前匹配中能够匹配到 S 串中最远位置的位置为 l，这个最远的位置为 r。那么此时有：

S[l...r]=T[1...r-l+1]

即

S[i...r]=T[i-l+1...r-l+1]

此时求 extend[i] 即相当于求 T[i-l+1...n] 与 T 的最长公共前缀。假设我们已经求出了一个数组 nxt，nxt[i] 表示 T[i...n] 与 T 的最长公共前缀长度，那么在这里相当于是求的 nxt[i-l+1]。设这个值为 tmp，那么如果 i+tmp<=r 则证明这个 tmp 可以取到，否则我们就把 ext[i] 调到 r 这个位置，然后继续向后匹配即可。复杂度 O(m)。

另外，求 nxt 数组的过程相当于是自己对自己进行一次以上操作，所以复杂度 O(n)。这就是 exKMP 和 KMP 最大的相似之处。

模板题 AC代码

六、子序列自动机

考虑先对 $T$ 中出现的值维护一个下标集合，每次进来 $S$ 之后从前往后扫，在当前位二分搜索当前值在 $T$ 中的下标集合中第一个大于当前位置的位置，把指针移过去。一直这样做看看能否移到最后即可。 [模板题](https://www.luogu.com.cn/problem/P5826) [AC代码](https://www.luogu.com.cn/record/60264853) **七、后缀自动机** 后缀自动机（SAM）是一个有限状态自动机，表示为一个有向图，分两部分：DAWG 和 parent 树。后缀自动机的定义是接受且仅接受串 $S$ 的所有子串，最小化节点个数。 DAWG 是一个 DAG。每个节点表示一个或多个 $S$ 的子串。起始节点对应 $\varnothing$。每条转移边都只代表一个字符。从起始节点开始的每一条路径都唯一对应 $S$ 的某个子串（或者说，某些本质相同的子串）。每个节点代表的字符串是**某些前缀长度连续的后缀**，每个点维护三个信息：$\min_u,\max_u$ 分别表示最小和最大长度的串，$\mathrm{end}_ u$ 表示这个节点表示的前缀集合。 定理 1 任意两个点的 $\mathrm{end}$ 集合互不相同。 证明：相同的话直接合并即可。 parent 树是一棵树。$u$ 的 parent 指针指向 $v$ 当且仅当 $|\min_u|=|\max_v|+1$，且 $v$ 代表的子串均为 $u$ 代表的子串的后缀，记作 $\mathrm{next}_ u=v$。所有节点作为以起始节点的为根的树，所以称为 parent 树。 定理 2 $\mathrm{end}_ u\subsetneqq \mathrm{end}_ {\mathrm{next_ u}}

这个很显然吧。真包含而不是包含是因为定理 1。

SAM 的构建：增量法。考虑在已经建出的 S 的 SAM 上扩展出 S+c 的 SAM。考虑下图：

Case 1：没有 $v_3

即 start=v_2，扩展出来的 u 点的 parent 应该为 start。

Case 2：\max_{d}=\max_{v3}+1

这个就正常建，然后把 u 的 parent 设成 d。

Case 3: \max_d\not= \max_{v3}+1

也就是说，本来是这样:

然后，v3+c 和 x1+c,x2+c 的 \mathrm{end} 集合出现了变动，这时候我们需要把 d 裂成两个点 v,dd，其中 v3\to v 表示 \mathrm{end} 集合发生变动的那些后缀，dd 是剩下的那些，然后就变成了这样：

my SAM code：

inline int newpos(std::array<int,M> nson,int nlen){return ++ptot,len[ptot]=nlen,swap(son[ptot],nson),ptot;}
inline void insert(int c){
    int p=lastpos;int u=newpos(boom,len[p]+1);cnt[u]=1;
    while(p&&!son[p][c]) son[p][c]=u,p=nxt[p];
    if(!p) return lastpos=u,nxt[u]=1,void();
    int d=son[p][c];
    if(len[d]==len[p]+1) nxt[u]=d;
    else{
        int v=newpos(son[d],len[p]+1);
        nxt[v]=nxt[d],nxt[d]=v,nxt[u]=v;
        while(p&&son[p][c]==d) son[p][c]=v,p=nxt[p];
    }
    lastpos=u;
}

SAM 可以解决以下几类问题：

一、判断一个串在另一个串里是否出现

对一个串建 SAM，拿另一个串在上面跑即可。如果没出现还可以顺带算出最长的出现了的前缀。

二、本质不同子串个数/某个子串的出现次数

这个建出 SAM 来之后在 DAWG 上 dp 或者在 parent 树上计算都行。

三、所有不同子串的总长度

这个跟上面差不多，可以在 DAWG 上 dp 计算，也可以利用 parent 树直接计算。

四、字典序第 k 大子串

对 SAM 上每个点求一个 b_i 表示从这个点开始往后走能走到的本质不同的子串个数。然后拿 k 在自动机上跑即可。

练习

[模板]后缀自动机

拆出来的点贡献为 0，其他贡献为 1，在 DAWG 上统计一个后缀和即可。

这个也一样 Fake News (hard)

不同子串个数

每个点 u 代表 len_ u-len_{nxt_u} 这么多串。这个也可以 DAWG dp 求得，不过太麻烦了。

这个题也一样 [SDOI2016]生成魔咒

LCS最长公共子串

给一个串建 SAM，另一个串在上面跑。

[TJOI2019]甲苯先生和大中锋的字符串

拿出出现次数为 k 的点，给这个点表示的长度区间 +1，这个可以使用差分解决。

Lexicographical Substring Search

本质不同第 k 小。上面讲了做法。

[TJOI2015]弦论

这题比上面那个题多结合了计算每个串的出现次数。

[BJOI2020]封印

对 T 建 SAM，拿 S 进去跑，可以得到每个 S 的前缀 S_i 的最长匹配后缀长度 sl_i。那么对于一个询问 [l,r]，答案就是 \max_{l\leq i\leq r}\{\min(sl_i,i-l+1)\}。

里面这个 \min 很难解决，我们考虑二分答案长度 mid，这样就可以只询问 [l+mid-1,r] 的 sl_i 的 \max，这个使用 ST 表可以 O(1) 解决。总复杂度 O(n|\Sigma|\log n)。

Cyclical Quest

循环同构的话很容易想到把串延长一倍，跑的时候找所有长度为 n 的公共子串的出现次数即可。

Match & Catch

虽然 n,m\leq 5000，但是这题是 O((n+m)|\Sigma|) 的。首先建 S 的 SAM，拿 T 上去跑可以得到 T 每个前缀的匹配区间（在 S 中只出现一次）。接着建 T 的 SAM，也可以求出每个前缀在 T 中只出现一次的区间。做一个区间交，取一个全局 \min 即可。

Sevenk Love Oimaster

对 n 个串建广义 SAM，每个点开一棵线段树维护 parent 树子树内的所有点都被哪些串走到过。这个直接线段树合并即可。注意分裂出来的点也需要update（我也不知道为何，反正不update会WA）。

[ZJOI2015]诸神眷顾的幻想乡

把所有叶子拎起来当根，合并成一棵trie之后建广义 SAM（我直接每个叶子直接跑的，每次 lastpos 重置，也可过）。

Paper task

统计一个后缀和数组 suf_i，其中 ) 为 1，( 为 -1，那么一个子串 s_{l,r} 是一个合法括号序列，当且仅当 \min_{l\leq k \leq r}suf_k\geq suf_{r+1}，并且 suf_l=suf_{r+1}。

我们对这个串建立 SAM 之后，每个点表示的是某个前缀的一段区间的后缀。限制出来之后，可以使用 ST 表配合 vector 来找出满足上述限制的位置统计答案。总复杂度 O(n\log n)。

[CTSC2012]熟悉的文章

对模式串建广义SAM，对于每个匹配串，首先求出 sl_i 表示以 i 为结尾的后缀的最长匹配长度。设 dp_i 表示 1\sim i 的最长匹配长度和，二分答案 mid 之后，有如下 dp 方程：

dp_i=\max(dp_{i-1},\max_{i-sl_i\leq j\leq i-mid}dp_j+i-j)

发现这个 i-sl_i 和 i-mid 都单调不减，所以可以直接单调队列优化 dp，复杂度 O(|s|\log |s|)。