字符串杂题记录

字符串刚刚入门。

考的少就贼亏。

Aho-Corasick AutoMaton

需要谨记的一点就是，$\rm{ACM}$ 跳的是 最长公共后缀，而不是 最长公共前后缀 。

不要和 $kmp$ 搞混了，千万不要相信什么 $\rm{ACM}$ 就是 $kmp$ 上树，千万不要。

Suffix AutoMaton

$\rm{SAM}$ 的一个节点储存字符串 $endpos$ 集合一样，这玩意可以用线段树合并求。

$\rm{SAM}$ 走 $ch$ 边相当于往后面加字符，跳 $fail$ 相当于删去一段前缀。

$\rm{SAM}$ 和 $\rm{ACM}$ 上做串的匹配是同一个道理，跳 $fail$ 都是删去一段前缀，每一次加入 $T$ 的后一个字符就跳 $fail$ 找到匹配的节点。

$\rm{LCP}$ 可以对反串做 $\rm{SAM}$，然后同时把位置反转，询问 $\rm{LCP}$ 等价于询问 $fail$ 树上 $lca(pos_i,pos_j)$ 节点的 $len$ 。

题目集合：

Loj #6401. yww 与字符串

设 $f(i)$ 表示 $[i,f(i)]$ 包含了不超过 $k$ 个坏字母，而 $[i,f(i)+1]$ 包含了至少 $k+1$ 个坏字母，如果 $[i,n]$ 包含了不超过 $k$ 个坏字母，那么 $f(i)=n$ ，同时设 $g(i)=f(i)-i+1$ 。

若一个字符串的 $endpos$ 集合为 ${a_1,a_2,\cdot,a_m}$，那么令该串的长度为 $len$ ，如果 $\forall i\in[1,m],g(a_1-len+1)\geq len$ ，那么该串就是满足条件的。

建出 $\rm{SAM}$ 后每一个节点维护 $fail$ 树上的子树内的 $g$ 的最小值，也就是长度限制，然后计算贡献即可，时间复杂度 $O(n)$ 。

「USACO17DEC」Standing Out from the Herd

建广义 $\rm{SAM}$ ，插入一个字符的时候对所有加入的子串打标记，也就是对该节点到根节点路径上的所有节点全部打上标记，可以离线 $dfs$ 的时候顺带更新标记。

如果一个节点拥有来自两个甚至更多串的标记或者这个节点没有标记，那么显然是不会计算贡献的，否则这个节点的贡献就算到其标记串的答案上。

Luogu P5212 SubString

查询一个串可以暴力找到该串的节点，然后出现次数就是节点的子树和。

如果不是强制在线的话就是一道模板题。

强制在线，意味着需要支持给某个点插儿子，然后查询节点子树和。可以用 $\rm{LCT}$ 维护。

同样的考虑一个经典问题：

Luogu P6292 区间本质不同子串个数

将询问离线下来，推进右端点，用线段树维护左端点的答案。

每一次插入了新的右端点，就会使得一部分串的” 最后出现位置” 产生变化，具体的就是当前节点到根节点路径上的所有节点均需要修改” 最后出现位置”，考虑用 $\rm{LCT}$ 维护 $\rm{SAM}$ 的 $fail$ 树，更新操作也就是 $access$ ，这样做的时间复杂度可以参考 $\rm{LCT}$ ，因为有线段树，所以总时间复杂度为 $O(n\log^2 n)$ 。

Luogu P4402「CTSC2012」熟悉的文章

首先二分 $\rm{L}$ 很显然，考虑如何 $check$ 。

设 $dp(i)$ 表示前 $i$ 个元素分成若干段的最大值。

转移的话从 $dp(j)$ 转移过来，其中 $j\in[i-val_i,i-L]$ ，$val_i$ 的意义就是以 $i$ 结尾的 $S$ 的前缀，满足条件 (即出现在前 $m$ 个串中) 的所有后缀中长度最大的。然后因为转移区间的左右端点一定都是单调不减的，所以可以用单调队列优化这个 $\rm{DP}$ 。

另一方面，考虑如何求出 $val_i$ ，将 $m$ 个串建一个广义 $\rm{SAM}$ ，然后按照「NOI2018」你的名字 一样的做法在上面暴力跳求出 $val_i$ 即可。

总时间复杂度 $O(n\log n)$ 。

暴力跳的部分，参见你的名字简解：

Loj #2720.「NOI2018」你的名字

首先考虑 $l=1,r=|S|$ 的做法。

直接求没出现的不好做，考虑求 $T$ 和 $S$ 的最长公共子串个数，先不考虑” 本质不同” 的限制。也就是说对于每一个 $i\in[1,|T|]$，求出 $T$ 的这个前缀和 $S$ 匹配的最大后缀长度，设其为 $val_i$，那么 $Str(val_i,i),Str(val_i+1,i),\cdots,Str(i,i)$ 都是不满足的。

现在考虑怎么求，对 $S$ 建立 $\rm{SAM}$，然后走 $ch$ 边就意味着往当前串后面加字符，走 $fail$ 边意味着删除当前串前面的一段。现在加入 $T$ 的第 $i$ 个字符 $c$，当前的匹配长度是 $val_i$ ，然后如果当前节点有 $c$ 的出边，那么意味着当前串后面加上 $c$ 也是在 $S$ 中出现过的，直接走过去，然后匹配长度加 $1$ ，否则跳 $fail$ 删除前缀直到有 $c$ 的出边。如果跳到根了还是没有出边，意味着这个 $c$ 完全就没出现过，匹配长度是 $0$ ，接下来也要重新从根节点开始匹配。

问题就在于同一个合法的 $T$ 的字串只能算一次，那么建 $T$ 的 $\rm{SAM}$ 后，直接在上面统计即可，这个时间复杂度是 $O(T)$ 的。

考虑满分做法，唯一的差别就在于暴力跳的过程，也就是说可能当前节点有 $c$ 出边，但是所到达的位置不在 $[l,r]$ 内，这个时候用线段树合并求出每个节点的 $endpos$ 集合，然后每次走 $c$ 出边的时候判断一下是否在合法区间内即可，时间复杂度就多了个线段树的 $\log$ 。

Luogu P5576「CmdOI2019」口头禅

考虑最长公共字串的做法，就是对于两个串，一个串建 $\rm{SAM}$，然后一个串丢到上面跑，跟上面两题差不多，对于一个区间暴力做的话就是选定一个串，然后对其他所有串建立 $\rm{SAM}$ 依次丢到上面跑，假设被选的串长度是 $|S|$，总长是 $len$，时间复杂度是 $O((r-l+1)|S|+len)$，显然 $S$ 选择最小的最优。

考虑满分做法，因为允许离线，所以可以将所有操作丢到一起做，每一次确定一个 $mid$，然后考虑猫树一样的想法，对区间内的所有串，把 $Str(mid)$ 分别丢到这些串的 $\rm{SAM}$ 上匹配，$res(i,j)$ 表示 $Str(mid)$ 的 $[1,j]$ 前缀丢到 $Str(i)$ 的 $\rm{SAM}$ 上匹配得到的最大长度。

猫树分治，意思就是到了每一层的分支区间，以 $mid$ 为中点，对于 $i<mid$，记录 $[i,mid]$ 区间的贡献，$i>mid$ 就记录 $[mid,i]$ 区间的贡献，然后对于当前询问，如果询问越过了 $mid$，那么可以直接完成查询，否则的话看看丢左边还是丢右边。

猫树，跟线段树一样，难支持修改，建树 $O(n\log n)$，查询 $O(1)$，主要思想就是对于每一个树上节点，设当前区间为 $[l,r]$，假设维护的区间和，那么当前节点记录一下 $[l,mid],[l+1,mid],\cdots,[mid,mid],[mid,mid+1],\cdots,[mid,r]$ 所有区间的和，然后查询的时候当 $l\leq mid,r\geq mid$ 的时候，就直接返回答案了，然后因为有办法直接定位到满足 $l\leq mid,r\geq mid$ 的节点，所以查询的时间复杂度是 $O(1)$ 的。

猫树分治就是借鉴了猫树对每个节点做标记使得查询复杂度很低的思想。

这里的话同样的是做 $res$ 的前缀 $\min$ ，然后按照上述方式处理即可。

对于怎么找 $mid$ 的话不能一次直接找最小值，可能最小值很靠左边或者右边，这样的话分治层数就很深，考虑随机，得到当前分治区间的串长的最小值后，乘上一定值，然后将所有小于等于当前值的串放在一起选中间那个作为 $mid$，这里的一定值我选的 $1.919810$，好像 $1.14514$ 也跑的挺快？

层数大概比 $\log$ 多一点。因为每一个串都会在一层被最多计算一次，也就是说当前分治区间，跳 $\rm{SAM}$ 的时间复杂度是 $|Str(mid)|$ 跳区间长度次，然后统计答案的话也是区间长度乘上 $|Str(mid)|$ 。

设总和为 $A$，因为总和不变，最劣一定是要使最小值尽可能的大，那么一共 $n$ 个串，每一个串的长度为 $\frac{A}{n}$，层数为 $L$，那么复杂度大概是 $O(L\times n)$，$L$ 大概是 $\log$ 级别，因此时间复杂度大概是对的。

以上是瞎算的时间复杂度，有错直接删。

CF235C Cyclical Quest

对于每个询问串，复制一下接在后面，然后依然考虑按照你的名字做法暴力跳，找串。

设当前询问串为 $T$，对于一个 $i\geq n$，以 $i$ 结尾的这一个前缀，如果匹配长度大于 $|T|$，说明当前循环串出现了，但是长度可能不对，因为要找的是出现次数，于是可以直接跳 $fail$，找到长度正确的节点计算 $siz$ 即可，需要注意的是一个节点只能被计算一次，也就是相同的串不能被计算多次，否则第二个样例就过不去。

每一次跳到的节点打个标记就完事了，清楚标记的时候记录一下标记打在哪些节点即可。

时间复杂度 $O(|S|+\sum |T|)$ 。

所以说这个直接在 $\rm{SAM}​$ 上找串也是一个常见套路 …… 时间复杂度就是要找的串的长度。

CF427D Match & Catch

建立广义 $\rm{SAM}$，然后对于每一个节点记录一下在 $A$ 串中的出现次数和在 $B$ 串中的出现次数，这个插入后 $dfs$ 一遍就可以求得。

最后只需要将所有节点扫一遍就完事了。

CF452E Three strings

同样的也是简单题，跟上题想法差不多。

每个节点记录一下 $A,B,C$ 的出现次数，然后将所有节点扫一遍，对答案的贡献就是一段区间加，差分处理即可。

CF1073G Yet Another LCP Problem

首先 $lcp(i,j)$ 的定义是 $i,j$ 两个后缀的最长公共前缀的长度。

然后在 $\rm{SAM}$ 的 $fail$ 树上，两个节点的 $lca$ 的意思就是两个前缀的最长共后缀。

于是建反串的 $\rm{SAM}$ ，然后将位置翻转即可，这样 $lcp(i,j)$ 就是 $fail$ 树上 $lca(pos_i,pos_j)$ 的深度了，这里 $pos_i$ 指的是包含了 $Str(1,i)$ 的唯一节点的编号。

求 $lcp$ 就把反串建出 $\rm{SAM}$ 然后将位置翻转一下后求 $fail$ 树上的 $lca$ 即可。

现在的题意就是给你两堆点，让你求其 $lca$ 深度之和。

考虑设 $sum(i,j)$ 表示 $i$ 的子树中 $j=0/1$ 组元素的个数，合并的时候更新答案即可，时间复杂度 $O(nq)$ 。

因为有 $\sum|A|,\sum|B|\leq2\cdot 10^5$，考虑每次询问对这些关键点建立虚树，然后在虚树上面 $\rm{DP}$ 即可。

CF666E Forensic Examination

也算是比较容易的一眼题了。

考虑只有一个 $T$ 怎么做，建 $T$ 的 $\rm{SAM}$，然后设 $pos_i$ 表示拥有串 $Str(1,i)$ 的节点编号，然后跳 $fail$ 就是删一段前缀，每一次询问 $l,r$ 的答案就从 $pos_r$ 开始倍增定位节点，然后出现次数的话就将 $T$ 求个子树 $siz$ 即可。

现在有一堆 $\rm{T}$，无脑线段树合并即可，线段树上每个节点维护一下最优位置和对应出现次数即可。

懒得判是不是找不到对应节点，所以把 $S$ 也丢进广义 $\rm{SAM}$，但是不计算 $siz$。

注意空间问题，要卡的紧一点，不然会 $\rm{MLE}$ 。

吐槽一下，暴力跳 $fail$ 定位串比倍增跳 $fail$ 定为串要快 … ，总时间快了 $10s$ 左右 …

CF1037H Security

显然如果一个串的子串没出现过，那么这个串也一定没出现过。

那么答案一定形如 $Str(1,i),i\leq |T|$ 后面跟一个字符，这个字符的字典需要满足比原来的下一个字符要大即可。

那么暴力找所有可能的最优答案了，显然 $i$ 越大越好，从大往前找，然后线段树合并维护 $enspos$ 集合判断一个串是否在区间中出现过即可，询问复杂度是 $O(|T|\log |S|)$ 。

SP8222 NSUBSTR – Substrings

直接 $\rm{SAM}$ 后写个区间 $\max$ 的线段树即可。

Luogu P3181「HAOI2016」找相同字符

建广义 $\rm{SAM}$ 后记录子树 $a,b$ 的和然后算贡献即可。

Luogu P2336「SCOI2012」喵星球上的点名

先建广义 $\rm{SAM}$ 。

然后令 $pos_i$ 表示第 $i$ 个询问代表的点编号。

对于第一问相当于问 $pos_i$ 子树内的颜色个数，线段树合并即可，时间复杂度 $O(n\log n)$，注意空间然后选择线段树合并的写法。

对于第二问，当前喵的一个节点，被叫道的次数就是其到根的路径上的 $pos$ 的个数，但是直接算可能会重，求个虚树然后每个点统计一下自己到父亲路径上的点数就完事了。

当然第二问还有其他很多的做法，愿意的话当然能线段树合并？不过虚树好写好调，时间复杂度 $O(n\log n)$ 。

细节很少。

Luogu P2414「NOI2011」阿狸的打字机

首先题目给出的串就比较迷，选择建 $\rm{Trie}$ 即可。

然后考虑 $\rm{ACM}$，对于一个串 $x$ 如果在串 $y$ 中出现次数，一定是从串 $y$ 每个后缀的结束节点跳 $fail$，然后跳到 $x$ 的位置就加一这种。

考虑从 $x$ 统计贡献，因为 $fail$ 是一棵树，$x$ 相当于要统计子树内有多少 $y$ 的后缀结束节点。

考虑直接遍历 $\rm{Trie}$，进入节点的时候加入贡献，退出节点的时候删除贡献，每个点就最多被操作两次，复杂度就对了。

$Str(x)$ 在 $Str(y)$ 中出现了多少次，$\rm{ACM}$，然后对于每个 $Str(y)$ 的子串一定是从某个前缀跳 $fail$ 得到的，找到 $x$ 的节点，出现次数即是 $x$ 子树内 $y$ 前缀点的个数 。

丢在一起直接在 $\rm{Trie}$ 上跑一遍是个不错的选择。

Bzoj #4231. 回忆树

细节有点多。

考虑将路径拆开，首先是 $u\rightarrow lca$ 路径上的出现次数，然后是 $lca \rightarrow v$ 路径上的出现次数，最后是” 越过” $lca$ 的串个数，分三类统计。

第一类，建立所有询问串的反串的 $\rm{ACM}$，然后丢到整棵树上跑，将询问存到对应的点上。

• 注意这里的点是原树点而非 $fail$ 树点。
• 具体跑的方法就是，从原树根节点开始，存一下当前走到 $\rm{ACM}$ 上了哪个节点了，原树走向哪个儿子，$\rm{ACM}$ 就对应转移，当没有对应出边的时候就需要跳 $fail$ (其实求 $fail$ 的时候就搞定了，直接走就完了)。
• 到达当前的原树节点 $u$ ，对应 $\rm{ACM}$ 的节点为 $t$ ，$t$ 作为当前的串，将 $u$ 中的询问都拿出来，直接查询对应节点的子树和即可。
• 用 $\rm{BIT}$ 维护每个点的贡献以及支持查询子树和，操作方法同” 阿狸的打字机”。

第二类，建立所有询问串的 $\rm{ACM}$，然后丢到整棵树上跑，将询问存到对应的点上。

跑的方法根第一类一样，而且可以丢在一起跑：

void get_ans(int u,int t1,int t2) {
    bit[0].update(acm[0].dfn[t1],1);
    bit[1].update(acm[1].dfn[t2],1);

    for(Query now:q[u]) {
        int id=now.id,p=now.typ,v=now.val,k=acm[p].pos[id];
        ans[id]+=v*bit[p].query(acm[p].dfn[k],acm[p].dfn[k]+acm[p].siz[k]-1);
    }
    for(Edge_Node now:son[u]) {
        int v=now.to,c=now.val;
        if(v==fa[u][0]) continue;
        get_ans(v,acm[0].ch[t1][c],acm[1].ch[t2][c]);
    }

    bit[0].update(acm[0].dfn[t1],-1);
    bit[1].update(acm[1].dfn[t2],-1);
}

$t_1,t_2$ 分别表示两个 $\rm{ACM}$ 上的当前节点编号，$u$ 表示原树当前节点编号。

第三类，直接搞下来暴力 $kmp$ ，因为长度是 $O(|S|)$ 的，总长度是 $O(\sum|S|)$ 的。

注意的细节有一点就是拆询问，$dep$ 为一个节点的深度，那么加上的贡献在 $u$，就需要在 $u$ 的深度为 $dep_{lca}+len-1$ 的祖先减去贡献，因为串一定不能包含 $lca$ 这个点，不然有可能算两次。

写成 $dep_{lca}+len-2$ 了调了较久。

然后由于询问总长的限制，$kmp$ 的复杂度是对的，然后有一题加强版，需要优化 $kmp$，暂时不敢动，贴个链接 。

更新：

CF917E Upside Down

上接回忆树。

考虑所有在我们考虑范围内的合法匹配，将匹配从 $lca$ 分成两半，处理出：

• $u\rightarrow \cdots \rightarrow lca$ 路径形成的字符串，所有和 $S_k$ 某一个前缀一模一样的后缀中最长的后缀长度，记为 $L_1$ ，同样记这个最长后缀为 $T_1$ 。
• $lca\rightarrow \cdots \rightarrow v$ 路径形成的字符串，所有和 $S_k$ 某一个后缀一模一样的前缀中最长的前缀长度，记为 $L_2$ ，同样记这个最长前缀为 $T_2$ 。

所有在考虑范围内的合法匹配一定满足，分成两半后，前面一半长度不超过 $L_1$，后面一半的长度不超过 $L_2$ ，而且确定前面一半为 $T_1$ 的前缀，后面一半为 $T_2$ 的后缀。

对于这个 $S_k$，记合法匹配对于串的分割位置为 $P$，容易发现的是 $P$ 可以为 $L_1$，但不只为 $L_1$ 。

当前的分割位置为 $P$，意味着 $S_k[1,P]$ 是 $S_k[1,T_1]$ 的后缀，同时又满足 $S_k[1,P]$ 是 $S_k[1,T_1]$ 的前缀，这意味着合法的匹配方案一定满足 $S_k[1,P]$ 是 $S_k[1,T_1]$ 的某个 $\rm{Border}$ 。

那么求出 $S_k[1,T_1]$ 的所有 $\rm{Border}$，然后通过上面同样的道理可以知道 $S_k[p,|S_k|]$ 也一定是 $S_k[T_2,|S_k|]$ 的一个 $\rm{Border}$ ，于是也求出 $S_k[T_2,|S_k|]$ 的所有 $\rm{Border}$ 。

现在考虑计算拼合的方案数，枚举两边的等差数列，然后计算拼起来是否有解，相当于计算一个 $ax+by=c$ ，其中 $a$ 表示第一个公差，$b$ 表示第二个公差，$c$ 也就是长度 $-$ 两个首项只和，$exgcd$ 求出方程组后在看看有没有合法范围内的解即可。

最后就是求 $T_1,T_2$ 了，先考虑 $T_1$，将 $S_k$ 和 $u\rightarrow \cdots \rightarrow lca$ 形成的字符串 $R$ 翻转，求的就是 $R$ 的一个前缀和 $S_k$ 的一个后缀的匹配。

考虑将 $S_k$ 丢进 $\rm{SA}$ 。

对所有后缀排序后，考虑当前 $rk$ 对应后缀 $S_k[i,|S_k|]$，令 $S_k[i,|S_k|]$ 和 $R$ 的最长公共前缀长度为 $L$ ：

• 如果 $L=|S_k[i,|S_k|]|$，也就是说当前后缀已经匹配满了，那么显然这是一组可以用于答案的后缀。
• 如果 $L=|R|,L< |S_k[i,|S_k|]|$，如果当前后缀没有匹配满，但是路径上节点匹配满了，这一组后缀一定不能用于答案。
• 如果 $L< |S_k[i,|S_k|]|,L<|R|$，都没有匹配满，考虑下一个字符，比较大小。

二分 $rk$ 求解，对于第一个情况，显然将 $rk$ 增大，如果将 $rk$ 缩小的话匹配长度一定会减少，第二个情况，如果将 $rk$ 增大一定不能得到解，因为要使得字典序加大一定是往后添加字符或者改变某个字符，而这样无论如何都不可能使得后缀匹配满，所以只能将 $rk$ 变小。

第三种情况，如果下一个字符 $R$ 的更大，那么显然要将 $rk$ 增大，在维持之前匹配好的字符同时将当前字符增大，否则就是将当前字符变小，$rk$ 变小。

所以这是可以二分的。

需要注意的就是因为没匹配满的话是按照字典序继续找的，所以有可能 $\rm{LCP}$ 比选定串短，这样的话直接暴力跳 $fail$ 即可，$fail$ 指 $kmp$ 的 $fail$ 。

最后将二分出来的结果检查一下就好了。

细节很多，写了 $10k$ 。