字符串

· · 个人记录

前言：

符号与标识：

*：表示有总结性的知识点。

\@：表示总体思路/算法。

!：表示重要的东西/切入点

#: 已复习的题目

知识点：

基本表示&定义：

周期：

Border：

前缀函数 Partical Match Table

for(int i=2; i<=M; i++) {
  for(pi[i]=pi[i-1]; pi[i] and a[i]!=a[pi[i]+1]; pi[i]=pi[pi[i]]);
  if(a[i] == a[pi[i]+1])    pi[i]++;
}

Border Tree/失配树

将 \pi_i 视作 i 的父亲节点构成的树。

Manacher

用于预处理 d_i 表示以 i 为中心的最长回文半径。

原理在于维护当前 (l, r) 表示右端点最大的回文子串。

当 i\le r 时，可以把 i 反转到 j = l+r-i 从而继承 j 的部分信息。

P.S. 为了方便，通常在每个字符中间插入特殊字符 '#' 从而使回文串的长度为奇数。

示例代码：

for(int i=1, l=0, r=-1; i<=N; i++) {
    int k = (i>r ?1 :min(d[l+r-i], r-i+1));
    for(; 1<=i-k and i+k<=N and s[i-k]==s[i+k]; k++);
    d[i] = k;
    if(i+k-1 > r)   l = i-k+1, r = i+k-1;
}

Z 函数/扩展 KMP：

用于预处理 z_i 表示 LCP(S, Suf(S, i)) 。

优化原理跟 Manacher 差不多，同样维护 (l, r) 表示右端点最靠右的匹配后缀，即 S[i..i+z_i-1] 。

当 i\le r 时，z_i \ge min(z[i-l+1], r-i+1) 。

再这个基础上继续用朴素方法扩展即可。

z[1] = N;
for(int i=2, l=0, r=0; i<=N; i++) {
    if(i <= r and z[i-l+1]<r-i+1) {
        z[i] = z[i-l+1];
    } else {
        z[i] = max(0, r-i+1);
        for(; i+z[i]<=N and s[z[i]+1]==s[i+z[i]]; z[i]++);
    }
    if(i+z[i]-1 > r)    l = i, r = i+z[i]-1;
    // printf("z[%d]:%d, l:%d, r:%d\n", i, z[i], l, r);
}

后缀数组 SA：

Lyndon 分解：

AC 自动机：

以 Trie 的结构为基础，结合 KMP 的思想建立的自动机，接受且仅接受以某一个模式串作为后缀的字符串。

失配指针：

状态 u 的 fail 指针指向另一个状态 v，其中 v\in Q，且 v 是 u 的最长后缀（即在若干个后缀状态中取最长的一个作为 fail 指针）。

构建：

AC 自动机：

令 \delta(u, c) 表示结点 u 加上字符 c 会到达的状态。

求解方法显然可以通过跳 fail 链得到。

Query

对于文本串 s，状态 (u, i) 表示状态 u 时匹配到第 i 个字符，相等于状态 u 是 Pre(s, i) 的后缀。

而显然，对于 u 的 fail 链上祖先，都是 Pre(s, i) 的后缀。

所以答案是个类似树链加的东西。

Suffix Tree 后缀树：

Suffix Automata 后缀自动机：

基本概念&性质：

构建：

查询：

回文自动机 PAM：

基本概念：

结构：

构建：

应用：

例题：

Border

BSOJ4196 -- 【NOI2014】动物园/P2375 -- [NOI2014] 动物园

思路 1：

思路 2：

*BSOJ4616 -- 【POI2005】Sza-Template/P3426 -- [POI 2005] SZA-Template

思路 1：

思路 2：

Manacher

*AGC021D -- Reversed LCS

! * 如何想到区间 DP 的思路很重要

首先有一个结论：S 和 S 的反串的最长公共子序列 = S 的最长回文子序列。

于是考虑求解最长回文子序列：

考虑转移：

*HDU5371 -- Hotaru's problem

定义了一个序列它分为三个部分，最左端和最右端是相同的，左端和中间的是回文。求这样的序列最长是多少。

首先，“最左端和最右端是相同的，左端和中间的是回文”，说明中间和右端又是回文。

回文的题，现在学过的唯一专门算法只有 Manacher，考虑先把 d 数组求出来。

此时有一个思路：

这个思路本质上用了“左中、左右”的条件，考虑能否使用“左中、中右”条件。

BSOJ5485 -- 回文子串计数

板子。

SA：

*BSOJ4472 -- [NOI2015] 品酒大会/P2178 -- [NOI2015] 品酒大会

抽象出题目即为：LCP(i, j) \ge r 的数量。

先考虑第一问求解：

再考虑第二问：

P.S. 单调栈显然也是可以的。

注意细节，仔细分析。

*BSOJ1628 -- 识别子串

先写式子：

考虑如何入手这个式子：

考虑快速求这个东西：

BSOJ3410 -- 字符串识别

上面那道题的双倍经验。

*BSOJ3656 -- 【SCOI2012】喵星球上的点名/P2336 [SCOI2012] 喵星球上的点名

首先，有名和姓两个串比较麻烦，先考虑把他们用特殊字符链接得到 S_i 。

然后问题转化成：

多串对多串，显然做不了，于是考虑把所有串拼在一起。

先考虑对每个 Q_i 处理答案：

考虑统计 S_i 的答案：

*BSOJ3807 -- 【HAOI2016】找相同字符/P3181 [HAOI2016] 找相同字符

先写式子：\sum_{i=1}^{n}\sum_{j=1}^m\sum_{len=1} [S[i..i+len-1] = T[j..j+len-1]] 。

显然考虑用 h 展开后面的判别式：\sum_i\sum_j\sum_{len}[LCP(i, j)\ge len] 。

容易发现可以进一步转化：\sum_i\sum_j LCP(i, j) 。

转化成 h 的 min 过后显然可以通过单调栈/笛卡尔树解决。

* 这里讲一下笛卡尔树的注意事项：

*BSOJ5809 -- 【NOI2016】优秀的拆分/P1117 [NOI2016] 优秀的拆分

\@ 需要用到 SA 维护关键点的技巧。

显然先写式子，可以得到：

ans = \sum_i\sum_{len_1}\sum_{len_2}[LCP(i, i+len_1)\ge len_1][LCP(i+2len_1, i+2len_1+len_2)\ge len_2]

显然这样后面 len2 不好做，稍微改一下，改为 i 枚举中间点。

所以需要维护 f_i 表示以 i 结尾的 len 数量，g_i 表示以 i 开头的 len 的数量。

现在两种思路：

其中第二种可做。

技巧： 对于这种涉及到枚举 len 的，考虑往调和级数方面想，于是我们考虑每 len 维护一个关键点。

自动机

*CF1090J -- Two Prefixes

做题思路 1：

先考虑大体思路：

定一求一显然有两种方向，先考虑枚举 s 的前缀 i：

考虑枚举 t 的前缀 l（上文中的 i+j-k ）：

我们发现若先处理第二个条件的思路是不应该的，应该考虑先处理难的条件，再快速处理简单的。

发现不对，最上面的 (i, j, k) 实际上并不是计数，而是求存在 k 满足 (i, j, k) 的【 (i, j) 的数量】

CF1186C -- Vus the Cossack and Strings

P.S. 这是一道我打错题号的题，可能跟自动机无关。

做题思路 1：

先考虑枚举 a 的为 b 长度的子串，看能否快速 check：

*CF1168C -- And Reachability

做题思路 1：

抽象一下题意就是判是否存在 q 个区间里的子序列（头尾必选），满足相邻两项的“与”不为 0。

显然按位考虑，每个点对每一位向最近的点连边。

然后就是判两点连通性。

预处理每个点到第 i 位为 1 的最近的点即可。

查询时枚举 r 的每一位即可。

AC 自动机：

BSOJ5672 -- GRE Words Revenge/UVA1676 背单词 GRE Words Revenge

二进制分组 + AC-AM 即可。

但是我调了 3h。。。

自动机上 DP：

*CF1303E -- Erase Subsequences

显然对 s 建出自动机。

维护保证不相交，显然在枚举 s1/s2 长度后，同时进行匹配。

然后 DP 一下即可，并不困难。

*CF1383E -- Strange Operation

先考虑构造出一个仅接受合法的 01 序列的自动机：

考虑在这个自动机上 DP：

P.S. 前后的 0 似乎要单独处理一下？

*CF1575H -- Holiday Wall Ornaments

做题思路 1：

没啥思路，先考虑个二分：

做题思路 2：经过题解点拨后考虑先建出 KMP 自动机。

直接考虑 DP：

SP10502 VIDEO - Video game combos

做题思路 1：

多模式串匹配次数最值问题，优先考虑建出 AC 自动机：

P4052 [JSOI2007] 文本生成器/1162 -- 文本生成器

跟上一题似乎很像，只用多记录个 0/1 即可。

为了方便，可以转化成总数减去不合法的。

OJ 和 SPOJ 由于数据范围不同，需要写矩阵。

2428 -- 【HNOI2008】GT考试/P3193 [HNOI2008] GT考试

显然先建出 KMP 自动机。

然后可以列出较为显然的 DP 方程。

显然使用矩阵优化。

BSOJ2241 -- 【BZOJ3864】英雄遇见魔鬼Hero meet devil

做题思路 1：

先概括一下题意：

SAM

*CF235C -- Cyclical Quest

处理循环问题，显然考虑倍长后做类似双指针的东西。

相当于在 SAM 上做匹配，假设现在匹配到了：t[i-len+1, i] ，状态为 t。

P.S. 由于跳一次 fail，必然让 len--，所以有势能。

*P4112 [HEOI2015] 最短不公共子串

四种情况，分开求解：

P.S. 不需要实际 DP，可以直接 bfs。

P.S. 上面两种方法也可以用自动机解决。

PAM：

BSOJ4339 -- 【ural2041】Palindromes and Super Abilities 2

跟板子差不多，只要有新建节点就是 1，否则是 0.

BSOJ4200 -- 【APIO2014】回文串/P3649 [APIO2014] 回文串

统计回文子串出现次数板子。

BSOJ2118 -- 【HDU6599】我喜欢回文串I Love Palindrome String

有一个限制条件，稍微处理一下即可。

BSOJ4342 -- 【BZOJ2160】拉拉队排练/P1659 [国家集训队] 拉拉队排练

直接按 bfs 序倒叙排序即可。

*BSOJ2124 -- /CF17E -- Palisection

做题思路 1：

发现直接在 PAM 上做，由于缺乏下标上的信息，比较麻烦。

于是考虑用 PAM 求出一些信息，最后还是放到序列上来做。

注意到 PAM 能求出的，跟下标有关的，大概都是形如：以 i 结尾/前 i 的回文子串。

发现直接求相交很困难，考虑正难则反，转成求不相交的对数。

很显然，【前 i 个字符的回文子串】和【后 n-i 个字符的回文子串】显然是不交的。

但是如果直接这么统计，显然会重。

于是考虑用【前 i 个字符的回文子串】和【以 i+1 开头的回文子串】统计。

显然不重不漏。

P.S. CF 卡空间，要写链表 PAM。。。

*BSOJ4351 -- 【BZOJ4044】病毒的合成Virus synthesis/P4762 [CERC2014] Virus synthesis

做题思路 1：

首先，我们发现只要有回文串，就用 2 操作一定更优。

所以我们可以发现，答案一定是：一个回文串 + n-len。

于是我们令 f_u 表示形成 u 表示的回文串需要的代价：

然后就只需要维护 len 一半的 v 了：

注意，只应在偶回文串上转移。

/*

所以我们可以列出 DP 方程：

*/

BSOJ2309 -- 【BZOJ2565】最长双回文串

显然考虑枚举中间点。

然后就很显然了。

*CF932G -- Palindrome Partition

做题思路 1：

首先显然考虑 dp，由于是个类似回文的形式，所以应该考虑从中间点开始向两边拓展。

令 mid = \dfrac n2，即中间点。

设 f_i 表示处理了 [mid-i+1, mid+i] 的答案。

显然有转移：

考虑优化：

*BSOJ6216 -- 【5.22模拟 BZOJ5384】有趣的字符串题

求区间本质不同回文子串个数。

做题思路 1：

基本思路：

考虑 PAM 上每个节点的有效区间：

错误的，应维护左端点，而非右端点。

做题思路 2：

回文划分板子。

*CF906E -- Reverses

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.

To be continued.