do_while_true's blog

晚风中闪过 几帧从前啊

0%

「学习笔记」字符串 I

Posted on Edited on In

字符串 I．

约定

1-index．

$|s|$ 为字符串 $s$ 的长度，如果讨论中仅有一个字符串也称之为 $n$．

$s[l,r]$ 表示字符串 $s$ 的 $[l,r]$ 子串。

$pre(s,r)=s[:r]=s[1,r]$，前缀．

$suf(s,l)=s[l:]=s[l,|s|]$，后缀．

$a_i$ 第 $i$ 个 $a$，有时产生嵌套时为易于观看记作 $a[i]$．

自动机那部分，suffix link 和 fail 指的是一个东西，可能会混用。suffix link 更偏向于其结构，而 fail 更偏向于匹配。

哈希

科学的讲解

字符串哈希

将字符串的每一位看成多项式的一个系数，求其哈希值（多项式哈希）。

性质：字符串哈希是一个分治信息。

P2757

首先只有 $len=3$ 是有用的，那么大概就判断是否有 $a_j-a_i=a_k-a_j,i<j<k$．

这个 $j$ 很特殊，考虑枚举这个 $j$，然后记录它前面元素的桶，为 $1$ 是出现，为 $0$ 是没出现。那么就是判断 $a_j+k,a_j-k$ 不同就代表出现了一个等差子序列。没出现的话就相当于关于 $j$ 是个回文的，线段树维护哈希值即可。

集合哈希

对于多重集 $S$，直接将 $S$ 中的元素排序之后多项式哈希即可。

线性实现是，其实只需要按照某种方式排序即可，所以可以将 $S$ 中的元素插入到哈希表中，然后以某种方式遍历哈希表后将其多项式哈希起来即可。

树哈希

树蛙给出的哈希方法时，假如现在某个节点的子树们的哈希值是多重集 $A=\{a_1,a_2,\cdots,a_d\}$，然后树高（不是 dep）为 $i$ 的点用同一个哈希函数 $h_i$，然后用集合哈希将其哈希起来。

上面那个很难写，我从 uoj 的树哈希模板上抄来了一个很好写的树哈希方法：

1
2
3
4
5
6
7
8
void dfs(int x,int fa){
	siz[x]=1;has[x]=val[0];
	for(auto v:eg[x])if(v!=fa){
		dfs(v,x);
		has[x]+=(has[v]^val[siz[v]])+val[0];
		siz[x]+=siz[v];
	}
}

$val$ 是一个随机映射到某个数的随机函数。

大概就是将所有子树的 $hash$ 异或其 $val(size)$，求和，再加上儿子个数 $+1$ 个 $val(0)$．

错误率分析都不会！

Border 理论

border：$pre(S,i)=suf(S,i)\neq S$，则称 $pre(S,i)$ 为 $S$ 的一个 border．

在某些语境中亦指其长度。

性质一：一个串的所有 border 形成了一个全序关系，换而言之，border 的 border 依然是一个 border。

周期：正整数 $p$ 是串 $S$ 的周期，当且仅当 $p\leq |S|$ 且 $S_i=S_{i+p}$，如果 $p$ 还整除 $|S|$ 则称其为整周期。

性质二：周期的正整数倍依然是一个周期。

两个性质画图均容易验证。

结论：$p$ 是 $S$ 的周期当且仅当 $pre(S,|S|-p)$ 是 $S$ 的 border。

把定义写出来。

性质三：一个串的所有前缀的最短周期不降。

换而言之，KMP 跑出来的 $i-nxt_i$ 是不降的。如果能对应上最短周期，那么最短周期不变，否则最短周期会变长，并且小的那些不会再变得合法（从这里就开始失配了）。一个小性质。

弱周期引理：$p$ 和 $q$ 都是 $S$ 的周期且 $p+q\leq |S|$，那么 $\gcd(p,q)$ 也是 $S$ 的一个周期。

证明：辗转相减。

令 $p>q$，首先对于所有 $1\leq i\leq |S|-p$ 均有 $S_i=S_{i+p}$，对于所有的 $1\leq i\leq |S|-q$ 都有 $S_i=S_{i+q}$．

  • $1\leq i\leq |S|-p$ 均有 $S_i=S_{i+p}=S_{i+p-q}$
  • $q<i\leq |S|-(p-q)$ 均有 $S_i=S_{i-q}=S_{i+p-q}$

那么即证 $(p-q)$ 也是 $S$ 的周期，辗转相减即可得到结论。

周期引理：$p$ 和 $q$ 都是 $S$ 的周期且 $p+q-\gcd(p,q)\leq |S|$，那么 $\gcd(p,q)$ 也是 $S$ 的一个周期。

证明很难，记住结论就好。

引理：$S$ 中所有 $\leq \lfloor\frac{|S|}{2}\rfloor$ 的周期都是最短周期的倍数；等价地，$S$ 中所有 $\geq \lceil\frac{|S|}{2}\rceil$ 的 border 构成等差数列。

$\Rightarrow$ border 划分：$S$ 的 border 可划分为 $\mathcal{O}(\log |S|)$ 段值域上不交的等差数列。

考虑弱周期引理，长度 $\leq \lfloor\frac{|S|}{2}\rfloor$ 所有周期的 $\gcd$ 一定也是一个周期，并且是最短的周期，它的所有倍数也一定是周期。一个数的所有倍数就是等差数列，用 $|S|$ 减之得到的 border 也构成等差数列。从而可得引理。自然导出了 border 划分。

如何构造转向后文 “失配树” 的例题 “Luogu P5829 【模板】失配树”

P3538

需要证明那个做法是对的。注意到根据弱周期引理，所有整周期一定是最小整周期的倍数就可以了。

WC2016 论战捆竹竿

若求出了所有 $border$ 构成的集合 $A=\{a_1,a_2,a_3,\cdots,a_k\}$，那么原问题等价于询问 $\sum a_ix_i,x_i\geq 0$ 能表示出 $[0,w-n]$ 中的多少数。

如果仅考虑后面那个问题，是一个同余最短路，所以此处 $a$ 必然有某些性质，不难想到 border 划分使其形成了 $\mathcal{O}(\log n)$ 段值域上不交的等差数列。

假设现对于一等差数列 $a,a+d,a+2d,\cdots,a+kd$ 跑同余最短路，以 $a$ 为模数，则有连边 $x\to (x+d)\bmod a$，不难推出此将图划分为 $\gcd(a,d)$ 个不交的长度都相等的环。

对于每个环单独处理。以 $dis$ 最小的点作为起点，断环为链重新编号，写出贡献方式即为 $(q-p)\leq k$ 则 $dis_{q}\gets dis_{p}+(q-p)d$，于是可以用单调队列求解。

现在考虑从一个公差为 $a$ 的等差数列换到另一个公差为 $b$ 的等差数列，现在 $dis_i$ 重新定义为最小的 $x$ 满足 $x\bmod a=i$ 且 $x$ 能被表示出。欲求出以 $b$ 为模数的新的 $dis’_i$．

考虑 $dis_i$ 代表着，$dis_i+a\times k,k\geq 0$ 均可被表示出，通过其求 $dis’_i$ 类似，先将 $dis_i\to dis’_{dis_i\bmod b}$，然后问题变成了 $dis’_i+a$ 可以用来更新 $dis’_{(i+a)\bmod b}$，这和上一个问题是等价的，这不过这里的等差数列没有项数的限制可以只记一个前缀 $\min$．

每次用一个等差数列更新同余最短路的复杂度是 $\mathcal{O}(n)$，一共要更新 $\mathcal{O}(\log n)$ 次，所以总复杂度就是 $\mathcal{O}(n\log n)$．

KMP 和 失配树

KMP

KMP 解决的是单个文本串 $S$ 和单个模式串 $T$ 匹配的问题。它分为了两部分，求出模式串每个前缀的非自身的最长 border，现定义其为 next，以及利用模式串的每个前缀的 next 完成匹配。

首先考虑如何求出模式串 $T$ 每个前缀的 next，如果 $T[:j]$ 是 $T[:i]$ 的 border，那么一定有 $T[:j-1]$ 是 $T[:i-1]$ 的 border．于是从大到小通过暴力跳 next，对 $T[:i-1]$ 的所有 border 检查出最大的 next 即可。

由于每次代表 $S[:i]$ next 的 $j$ 最多 $+1$，所以跳 next 的次数均摊是 $\mathcal{O}(|T|)$ 的。那么这部分总复杂度就是 $\mathcal{O}(|T|)$．

然后考虑如何完成匹配，原理类似，$S[i-j+1,i]$ 和 $T[:j]$ 匹配，那么一定有 $S[i-j+1,i-1]$ 和 $T[:j-1]$ 匹配，所以在暴力匹配的过程中产生失配时，将 $j$ 不断跳其 next 检查即可。复杂度分析同理是 $\mathcal{O}(|S|)$ 的。

例题

CF1200E

每次加入一个串的时候在前面串合并结果的尾部截取同样长度的串，reverse 之后跑 kmp 就知道截掉多少，如果最长 border 大于后面那个串的串长继续暴力跳 border 跳出第一个小于等于后面串串长的 border。

P4824

由于 KMP 的复杂度是均摊的，所以任意回退状态会导致复杂度出现问题。

但是此题中复杂度是对的，因为只有匹配的时候会回退，回退的时候指针 $j$ 一定是变小的。依然可以均摊。

「HNOI2019」JOJO

next 的定义是，字符串的最长 border．

考虑如果没有二操作怎么做：

首先一个关键的性质就是相邻两次插入的字符不相同，这意味着对于一个 border，除了首尾两段不完整的段，中间的段必须完全相同。这提示我们只需要维护除了第一段以外的所有整段皆相同这样一个形式的 border，具体地：

每次插进 $x$ 个字符 $c$ 的二元组 $(c,x)$，对这个二元组跑类似 KMP 的东西，定义 $nxt_i$ 为最大的 $j$ 满足 $\forall k\in [1,j],c_k=c_{i-k+1}, \forall k\in[2,j],x_{k}=x_{i-k+1}, x_1\leq x_{i-j+1}$．类似 KMP 预处理 $nxt$，在预处理这个 $nxt$ 的时候需要记录一下 $(c_i,x_i)$ 已经匹配成功每次匹配成功的长度 $mxlen$，即可计算 $mxlen$ 应该增加多少，并且计算出对答案的贡献，一个等差数列求和的形式，具体的贡献形式。

现在就考虑怎么把这个东西可持久化掉。自然的想法是建出操作树，但是这样需要支持撤销，而这个 KMP 的复杂度也是均摊的，并不能支持撤销。

如果对这个 KMP 建立一个 KMP 自动机，也就是处理出 $f_{i,c,x}$ 表示在 $i$ 节点之后来了一个 $(c,x)$ 所走到的节点，以及 $g$ 表示答案应该产生的贡献。回顾上述 KMP 答案的贡献形式，容易发现在修改操作是一个区间赋值，所以可以用主席树维护所有的 $f_{i,c}$ 和 $g_{i,c}$．复杂度毛咕咕一下应该是 $\mathcal{O}(n|\sum|\log n)$

还有一个做法是考虑 border 划分。$nxt_i$ 实际上就是处理出了前 $i$ 个字符段的 border．它在字符串中对应着一个周期，由于相邻两个字符段的 $c$ 不同，所以其在 $(c,x)$ 形成的串中也是一个周期（这里周期的判定是要求逐个二元组完全相同）。

虽然在 $(c,x)$ 串中 border 的定义改变了，但是这个周期的定义不变，所以弱周期引理仍然满足，进而 border 划分依然满足。故在 $(c,x)$ 串中做 KMP 的时候，当一次 $j+1$ 和 $i$ 产生失配时，由于存在 $j-nxt_j$ 的周期，所以 $j$ 所在的 border 等差数列中前面的 border 都会失配，可以直接跳到前一个等差数列。

这样一次匹配的复杂度就是不均摊的 $\mathcal{O}(\log n)$ 的了。总复杂度就是 $\mathcal{O}(n\log n)$．这个做法的优点是字符集多大都能做，也启发我们普通的 KMP 字符串匹配往后匹配单个字符是可以利用 border 划分做到非均摊 $\mathcal{O}(\log n)$ 复杂度的。

失配树

$i$ 向 $i$ 的最长 border 连边，由于 border 的性质其形成了一棵树，前缀 $i$ 的所有祖先就是其所有 border。

基本应用：

  • 两个前缀的最长 border 就是它们在树上的 LCA。
  • 查询一个串长度 $\geq k$ 的最小 border 可以倍增求得。

HDU 7084 Pty loves string

怎么想到失配树？考虑一个子串 $S[l,r]$ 合法当且仅当 $S[l,l+x-1]=S[1,x]$ 且 $S[r-y+1,r]=S[n-y+1,n]$，由此想到 border：一个 $l+x-1$ 合法需要满足 $S[1,x]$ 是 $S[1,l+x-1]$ 的 border，而根据 border 的子结构性质，所有合法的 $l+x-1$ 即为 $x$ 在失配树子树中的所有点。

对于合法的 $r-y+1$ 也同理，只需要反过来建一个失配树。于是问题变成了多次询问两棵树，每次询问两个子树中有多少个相同编号的点，直接做就是线段树合并，也可以转化成二维数点问题，从而扫描线 + 树状数组解决。时间复杂度 $\mathcal{O}(n\log n)$．

Luogu P5829 【模板】失配树

crashed nb/se 不过它解释为什么跳 $k\bmod d+d$ 确实有点迷，不懂为什么直接跳 $k\bmod d$ 会挂可以手摸一下峰峰峰的 hack，从 25 开始跳。

三个找等差数列的方法：

  • 倍增分块：$[1,2),[2,4),[4,8)\cdots,[2^k,2^{k+1}),\cdots$ 这么分块，然后断言每一块里面的 border 一定形成了一个等差数列。首先最后一块肯定满足，$\geq \lceil\frac{|s|}{2}\rceil$ 的 border 形成一个等差数列，对于中间的块同理，也就是对 $s[:2^{k+1}]$ 用那个结论。
  • 利用失配树：跳祖先过程中第一个 $v-nxt_v$ 和自身 $u-nxt_u$ 不同的 $v$，可以用倍增做到。
  • 后面要讲的：每次 $d=k-nxt_k,k\gets k\bmod d+d$．

简单做法就是建出失配树然后跳 LCA．但是 border 的性质很好，所以就来考虑一些小常数做法：

考虑一个等差数列在支配树上实际上就是一条链，而且端点具有祖孙关系。那么自然就想到了树链剖分，尝试利用 border 划分将整棵树进行剖分，使得从每个点往上跳一个树链相当于跳一个等差数列。那么问题就是怎么剖，怎么确定两个点是否在同一个等差数列上。

怎么剖，实际上就是对于一个 $k$，确定 $k$ 所在的等差数列的头在哪里。

  • $nxt_k\leq \lfloor\frac{k}{2}\rfloor$：它就是链头。
  • 否则，对于最短周期 $d=k-nxt_k$：考虑每次将 $k\gets k-d$，当 $d\leq \lfloor\frac{k}{2}\rfloor$ 的时候根据推 border 划分时的引理，$k-d$ 就是 $k$ 最长 border．否则就到了链头。考虑 $k\bmod d$，不断 $-d$ 的过程，只有最后一步会出现问题，所以链头就是 $k\bmod d+d$．

然后问题就是怎么判终止条件，以及会不会出现跳过 LCA 的情况

判终止直接看 $x\equiv y\pmod d$ 是否成立就行，这里 $x>y,d=x-nxt_x$。如果不成立那么肯定不在同一个划分出的链上。如果成立，画图可知 $y$ 是 $x$ 的 border，所以 $y$ 就是 $x$ 的祖先，而且 $x,y$ 在同一条划分出的链上时一定能判出来。注意这里严格来说并不是看它们两个是否在同一个等差数列上。

还是峰峰峰那个例子，树链是 $1\leftrightarrow 3\leftrightarrow 7\leftrightarrow 13\leftrightarrow 19\leftrightarrow 25$，1 和 25 能判对，7 和 25 能判对，但是 3 和 25 判不出。但是只要保证 $7\leftrightarrow 13\leftrightarrow 19\leftrightarrow 25$ 这条划分出的链上的点都能判出来，并且不会额外判错就行。

DFA

一个确定有限状态自动机（DFA）的组成：

  1. 非空有限的字符集 $\Sigma$；
  2. 非空有限的状态集合 $Q$；
  3. 开始状态 $start\in Q$；
  4. 接受状态的集合 $F\subseteq Q$；
  5. 转移函数 $\delta =Q\times \Sigma \to Q$．

也就是说，一个 DFA 由这样一个五元组组成，它可以一个字符一个字符地输入一个字符串，从 $start$ 开始，每次根据转移函数转移到下一个状态，如果最终停在终止状态，则称该自动机接受此字符串。

DFA 很像一个有向图，在 OI 中将其视作一个有向图即可。

一个应用是，将 dp 转移写成 DFA 的形式，然后压缩这个 DFA，然后在这个 DFA 上跑矩阵快速幂来优化转移。

另一种理解角度是，一类判定性 dp 实际上可以写成 DFA 的形式，而对其计数即为 dp 套 dp，对内层 dp 值域/转移的剪枝，即为对内层 DFA 状态的剪枝，从而优化。

例题：CF506E 鸽了

AC 自动机

尝试一下写出更本质的理解。

Trie 树和 AC 自动机的基本概念：略。

AC 自动机解决的是多模式串匹配问题。

AC 自动机的构建

定义 $tr_{x,c}$ 表示 Trie 树上 $x$ 节点通过字符 $c$ 走到的点。

$fail_x$ 指向 $x$ 节点代表的字符串在字典树中出现了的最长后缀。当只有一个串时，其即为 KMP 中的 next 指针（一个前缀的最长 border）。

构建方法一

考虑 $x$ 是由 Trie 中的父亲 $fa$ 通过 $c$ 转移边得到的。那么检索 $y=fail_{fa}$，若 $y$ 存在字符 $c$ 的转移边，则令 $x$ 指向 $tr_{y,c}$；否则，令 $y\gets fail_y$ 即不断跳 fail 检查是否有 $c$ 出边。若到了初始节点（Trie 的根节点）依然没有 $c$ 出边，则令 $fail_x$ 指向初始节点。

注意需要用 bfs 实现，因为 dfs 可能导致 fail 的 fail 还未处理而出现问题。

其时间复杂度为多少？

如果是给定若干模式串建出的 Trie 求 fail：对于每个串在 Trie 中自顶向下考虑尝试寻找 fail 的 $y$ 在最终 fail 树中的深度变化，每次向下走一个儿子 $y$ 深度最多 $+1$，每次暴力跳 fail 深度都会 $-1$，均摊下来总的时间复杂度就是 $\mathcal{O}(\sum |S|)=\mathcal{O}(n)$．

如果是像 阿狸的打字机 一样直接给定 Trie 求 fail 树：设总状态数为 $n$．在最终 fail 树上，对于每一个字符 $c$ 将 fail 树上所有有 $c$ 作为出边的点 $x$ 标记。那么对于每个被标记的 $x$，其代价为 $dep_x$ 减去祖先中最靠近 $x$ 的标记点的 $dep$．不难发现代价总和 $\leq$ 整棵树的大小。则对于每个颜色来说时间复杂度为 $\mathcal{O}(n)$，那么总的时间复杂度就是 $\mathcal{O}(|\Sigma|n)$，事实上这个上界也能卡到，构造一个链套菊花即可。

复杂度总结：如果内部用 unordered_map 存储转移边，可以做到 $\mathcal{O}(n)$ 的空间复杂度。给定若干模式串求 Trie 的 fail 时间复杂度是 $\mathcal{O}(n)$，直接给定 Trie 求 fail 的时间复杂度是 $\mathcal{O}(|\Sigma|n)$．

根据上面的分析，即有 $dep[x]\leq dep[fa_x]+1$（$dep$ 是在 fail 树上的深度，$fa$ 是 Trie 上的父亲）。让文本串在 AC 自动机上匹配的时间复杂度是均摊 $\mathcal{O}(|S|)$ 的。

在有些情况下需要求出一个新的转移函数 $tr_{x,c}$ 表示当前在 $x$ 节点，新来一个字符 $c$ 应该走到哪个点，那么引出了构建方法二，也是较为常用的一个构造方法。

构建方法二（更常用）

对 Trie 进行 bfs，每次搜索到一个点 $x$ 的时候处理出所有 $tr_x$ 以及 $x$ 所有儿子的 fail，具体地：

  • 若 $tr_{x,c}$ 已经存在，则 $fail[tr_{x,c}]\gets tr_{fail[x],c}$；
  • 若 $tr_{x,c}$ 不存在，则 $tr_{x,c}=tr_{fail[x],c}$．

时空复杂度均为 $\mathcal{O}(|\Sigma|n)$．

如果字符集特别大话，注意到 $tr_x$ 相对于 $tr_{fail[x]}$ 仅有 $x$ 有对应出边 $c$ 的哪些 $tr_{x,c}$ 会不一样，那么可以用可持久化线段树维护 $tr$，时间复杂度为 $\mathcal{O}(n\log n)$．

注：在 KMP 的例题 「HNOI2019」JOJO 中运用到了这个思路。

深入理解 AC 自动机结构

补充定义：

  • 称上面构建方法二中处理出的 $tr$ 为转移边。
  • 后文中提到一个字符串 $s$ 在 AC 自动机中的节点，即为 $s$ 不断走转移边所走到的节点。

前缀：已经学习过 Trie（就当我写了 Trie）对于一个文本串 $S$，所有满足是其前缀的模式串 $T$ 即为 $S$ 走 Trie 边经过的所有点（当然需要这个点代表某个完整 $T$，后面讨论到的也一样）。

后缀：

  • 首先考虑满足是文本串后缀的最长模式串前缀，就是 $S$ 在 AC 自动机里面走转移边走到的点；
  • 考虑 fail 树上的结构，在其上面跳一次父亲，相当于在字符串的前面删去若干个点得到的最长真后缀，那么 $S$ 走转移边走到的点在 fail 树上包括自己的所有祖先即为 $S$ 的所有出现了的后缀。

子串：

$S$ 的前缀，$T$ 作为其后缀：$S$ 走转移边走到的所有节点在 fail 树上的根链的并（如果不去重就是和）；或者考虑 $T$ 给 $S$ 贡献就是在 $T$ 的终止节点 fail 树子树加，$S$ 走转移边所有走到节点的权值和（不去重计数）。

$S$ 的后缀，$T$ 作为其前缀：$S$ 走转移边走到的终止节点，它的所有祖先在 Trie 树上的子树并（如果不去重就是和）；或者考虑 $T$ 给 $S$ 贡献就是在 $T$ 的终止节点 Trie 树上根链加，$S$ 终止节点 fail 树根链和。

（如果彻底理解了 AC 自动机的结构，这几种贡献方式自己推推就能推出来）

例题

P5599

强制在线构建 AC 自动机。

因为这个信息可以差分，给插入的和删除的各自维护一个 AC 自动机即可。

无论构建方法一/二都需要 bfs，所以并不能支持在线插入字符串。

对于这种只能离线构建的数据结构，当其需要支持在线插入时，实用的工具是二进制分组。

具体地，假设现在有 $n$ 个字符串，$n$ 的二进制拆分是 $2^a+2^b+2^c+\cdots$，那么给前 $2^a$ 个字符串单独建一个 AC 自动机，再给之后 $2^b$ 个字符串单独建一个 AC 自动机……插入一个字符串时，先给它单独建一个 AC 自动机，然后看如果同时存在两个大小为 $1$ 的 AC 自动机，就暴力重构为一个大小为 $2$ 的 AC 自动机，然后检查是否同时存在两个大小为 $2$ 的 AC 自动机，再检查 $4,8,\cdots$．考虑一个字符串至多会被重构 $\log$ 次，所以总复杂度就是 $\mathcal{O}(m\log m\Sigma)$，其中 $m=\sum |s_i|$．如果使用构建方法 1 复杂度可以去掉那个 $\Sigma$．

P2292

作一个 dp，$f_i$ 表示 $t[:i]$ 能匹配到哪里。

考虑这个怎么转移，就是 $t[:i]$ 如果有一个后缀 $s$ 是字典中的单词，那么 $f_i\gets f_{i-|s|}$，注意到不同的 $|s|$ 只有 $20$ 个，所以尝试预处理出每个 $t$ 的前缀中合法的 $|s|$ 有哪些。

首先由于 $|s|$ 只有 $20$ 个，所以可以拿一个 int 来压位，然后考虑对字典建 AC 自动机，那么 $t[:i]$ 的合法后缀就是它在 AC 自动机上匹配的时候在 fail 树上的祖先中的终止节点。这样就能很好预处理出了。

然后考虑 $f$ 的转移，它也能压位优化转移，也就是转移的时候记录 $f_i$ 它前面 $20$ 个 $f$ 的状态，转移的时候按位与一下。

P2336

题意有点绕啊。

大概是首先姓和名之间插入一个 # 这样相当于每次是一个 $y$ 在 $x$ 里面出现过，那么 $x$ 这只猫就要喊到。

第二问，对每个姓名串 $x$，查询点名串中有多少子串 $y$．子串怎么描述？是不是 $x$ 的所有前缀的后缀。对点名串作 AC 自动机，在 AC 自动机上就是 $x$ 走转移边走到的所有节点在 fail 树上的根链的并，查询这里面终止节点的个数。

第一问，对每个点名串 $y$，查询它是多少个姓名串 $x$ 的子串。考虑刚刚那个第二问，相当于这个节点被多少 $x$ 的所有走到的节点在 fail 树上的根链的并所覆盖。

那么问题就是在 fail 树上的根链并修改、单点查询。以及 fail 树上的单点修改，根链并查询。

根链的并实际上就是它们的虚树，先加上（or 修改）所有的根链长度，按照 dfn 排序后减去两两相邻 lca 的根链即可（最后一个也和第一个相邻）。

会这个题的话大概就能彻底理解 AC 自动机结构了吧（雾）

CF547E

考虑对这个 $s_k$ 在 $s_{l..r}$ 中出现，转化成以 $s_k$ 为后缀的串，其在 $s_{l..r}$ 中有多少次作为前缀出现。

那么把询问差分成一个 $s_{1..r}$，然后作扫描线，每次扫入一个 $s_r$ 的时候把它在 Trie 上的祖先都 $+1$，询问 $s_k$ 就询问 $s_k$ 在 fail 树上的子树和。也就是在 fail 树上单点 $+1$，子树求和，时间复杂度是 $\mathcal{O}(n\log n)$．

CF587F

先差分一下，求 $s_{1…r}$ 在 $s_k$ 中出现次数。

考虑答案是这样贡献的：对于 $s_{1..r}$ 每个字符串给它的终止节点 fail 树子树加，然后查询 $s_k$ 走到的所有点的权值和。

polylog 想不到，那就试试根号。既然尝试根号，就考虑按 $s_k$ 串长根号分治。记根号分治的界限是 $B$，默认 $n,m,q$ 同阶统一为 $n$．

$|s_k|\geq B$，只有 $\mathcal{O}(\frac{n}{B})$ 个 $s_k$，对于每个 $s_k$，预处理出每个节点在 fail 树子树中有多少个 $s_k$ 走过的点，每个串的贡献就是固定的一个值了，一共 $\mathcal{O}(n\frac{n}{B})$ 次单点修改，$\mathcal{O}(n)$ 次前缀查询，但是是修改完再查询，用个前缀和解决即可。

$|s_k|<B$，扫描线扫 $r$，每扫进一个 $r$ 在其终止节点 fail 树子树加，遇到一次询问暴力将经过的每个点的答案单点询问得到。一共 $\mathcal{O}(n)$ 次区间修改，$\mathcal{O}(nB)$ 次单点查询。

令 $B=\sqrt n$，$|s_k|<B$ 的部分用一个 $\mathcal{O}(\sqrt n)$ 区间修改，$\mathcal{O}(1)$ 单点查询的分块，即可做到总时间复杂度 $\mathcal{O}(n\sqrt n)$．

P3735

想不出来怎么讲得比这个题解好

扩展 KMP

有用吗？

基础

定义：字符串 $s$ 的 Z 函数定义为 $z_i=LCP(s[i:],s)$，也就是从 $i$ 开始的后缀与整个串的 LCP 长度。特别地，$z_1=0$（1-index）．

Z 函数的求解方式和 Manacher 十分类似。

对于 $i$，称 $[i,i+z_i-1]$ 为其匹配段，也称 Z-box．从小到大求解 $z_i$，并维护之前已经求得的右端点最大的 Z-box $[l,r]$．

  • $i>r$，直接暴力向后匹配求 $z_i$；
  • $i\leq r$，将图画出来，根据 $z$ 的定义，即得 $z_i\geq \min(z_{i-l+1},r-i+1)$，先令 $z_i\gets \min(z_{i-l+1},r-i+1)$ 然后向后暴力匹配。

注意在第二种情况下，如果 $z_{i-l+1}<r-i+1$，那么一定不会向后暴力匹配成功，否则与 $z_{i-l+1}$ 是 LCP 产生矛盾（画图理解）。

那么每次暴力匹配成功 $r$ 都会 $+1$，而 $r\leq n$，所以总的时间复杂度是均摊 $\mathcal{O}(n)$ 的。

对于两个字符串 $s,t$ 求 $s$ 的每一个后缀与 $t$ 的 LCP 长度也是同理，具体实现参考下面模板题的代码。其实也可以将 $t$ 和 $s$ 拼接起来，中间塞一个不与字符集中其他任意字符相同的特殊字符，正常求 Z，也是可以求出答案的。事实上，这两种做法本质相同。

例题

P5410

模板题，求 $t$ 的 Z，以及 $t$ 与 $s$ 的每一个后缀的 LCP．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
scanf("%s",s+1);
scanf("%s",t+1);
n=strlen(s+1);
m=strlen(t+1);
int l=0,r=0;
ll v=m+1;
for(int i=2;i<=m;i++){
	if(i<=r)z[i]=min(r-i+1,z[i-l+1]);
	while(i+z[i]<=m&&t[i+z[i]]==t[z[i]+1])++z[i];
	if(i+z[i]-1>r)r=i+z[i]-1,l=i;
	v^=1ll*i*(z[i]+1);
}
cout << v << '\n';
v=0;
l=r=0;
for(int i=1;i<=n;i++){
	if(i<=r)p[i]=min(r-i+1,z[i-l+1]);//注意这里是 z[i-l+1]
	while(i+p[i]<=n&&p[i]+1<=m&&s[i+p[i]]==t[p[i]+1])++p[i];
	if(i+p[i]-1>r)r=i+p[i]-1,l=i;
	v^=1ll*i*(p[i]+1);
}
cout << v << '\n';

CF1313E

考虑这个 $l_1$ 一定是 $s$ 的开头，$r_2$ 一定是 $t$ 的结尾，那么就考虑假如固定了 $l_1,r_2$ 之后怎么计算对答案的贡献。

一个河狸的想法是，固定 $l_1$ 之后可以通过 exkmp 求出 $LCP(a[l_1:],s)$，就知道 $r_1$ 能落在 $l_1$ 的 Z-box 里。同理也知道 $l_2$ 能落在 $r_2$ 的 Z-box 里。

假设 $LCP(a[l_1:],s)=p,LCS(b[:r_2],s)=q$，$a$ 选了 $x$ 个，那么 $b$ 选 $m-x$ 个，则 $[l_1,r_1]=[l_1,l_1+x-1],[l_2,r_2]=[r_2-(m-x)+1,r_2]$．

它俩有交当且仅当 $r_1\geq l_2$ 且 $r_2\geq l_1$，化简后可得 $l_1\leq r_2\leq l_1+m-2$，这是第一维限制。

然后再考虑满足条件的 $x$ 数量，$1\leq x\leq p,1\leq m-x\leq q$，也就是 $\max(1,m-q)\leq x\leq \min(p,m-1)$．

然后所有的 $p,q$ 都和 $m-1$ 取个 $\min$，这样符合条件的 $x$ 的数量就是 $p-(m-q)+1$，而且要满足 $p\geq m-q$，这是第二维限制。

于是变成一个二维数点问题。