[COCI2015-2016#5] OOP（Trie）
P6727 [COCI2015-2016#5] OOP - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
正反串分别建 Trie，可以搞出两个 dfn 区间，加之长度限制，三维数点。
有 \(O(n\log n)\) 做法。将字典串 \(S[1..m]\)，对所有 \(1\leq i\leq m\)，将 \(S[i+1,m]\) 的 hash 值插入到 \(S[1,i]\) 这个字符串在 Trie 树上的点。这样，询问就变成了，先找到通配符前的部分在 Trie 树上的位置，然后在子树中找有多少个 hash 值与通配符后的部分相等。离线所有询问，仅需一个 map。
[Guilin21H] Popcount Words（ACAM、倍增）
Popcount Words - Problem - QOJ.ac
对询问串建 AC 自动机。观察到结构有倍增性质，直接倍增。
\[S[0, 2^k)=S[0, 2^{k-1})+S'[0, 2^{k-1}) \]\(S'\) 表示所有字符 \(0\) 变 \(1\)，\(1\) 变 \(0\)。可以倍增求出每个 \(S[0, 2^k)\) 在 AC 自动机上的位置。我们可以将大串在线段树上拆成 \(O(n\log n)\) 个小串，小串不断倍增将经过次数传递下去，传递到最后一层就是答案。
无标题（ACAM）
将排列 \(a[1,n]\) 改写为一个整数序列 \(f(a)[1,n]\)，定义为 \(f(a)[i]=\sum_{j<i}[a_j>a_i]\)（什么康托展开）。那么本质相同就是 apply \(f\) 之后相等。
对询问排列 apply \(f\) 后建 AC 自动机，但是这个 AC 自动机的 fail 有讲究，每个点的出边是在这个点对应的排列中的排名，可能跳了一次 fail 之后排名会因为一段前缀被砍而骤降。
这里暴力跳 fail 的复杂度在给定多个串时是对的，给定 Trie 树是不对的。
[CF1801G] A task for substrings（ACAM）
A task for substrings - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
惊人的一步：\(ans[l,r]=ans[1,r] - ans[1,l-1] - somesubstr\)，其中 \(somesubstr\) 是所有 \(x<l\leq y\leq r\) 的出现在模式串中的 \(t[x,y]\) 的个数。这玩意竟然是可以做的，考虑令 \(A=t[x,l-1], B=t[l,y]\)，那么实际上可能的 \((A,B)\) 也就 \(\sum\) 模式串串长这么多，所以可以转化为二维数点，变成 \(t[1,l-1]\) 有后缀是 \(A\)，\(t[l,r]\) 有前缀是 \(B\)，也就是有两对子树关系，二维数点。是不是需要一些匹配技巧？
\(A\) 是 \(t[1,l-1]\) 的后缀：对所有正的模式串建 ACAM，则所有 \(A\) 都是 ACAM 的一个点。将 \(t[1,l-1]\) 在 ACAM 上跑，则 \(A\) 是其 fail 树上祖先。
\(B\) 的限制则是反串，顺带附赠一个倍增。
改成 \((A, B)\) 对其子树贡献，所以就是矩形加，单点查询的二维数点问题。
*[Nanjing23J] Suffix Structure（ACAM）
Suffix Structure - Problem - QOJ.ac
使用可持久化线段树维护 Trie 图，建立 AC 自动机。对除了根以外的每个节点 \(u\)，首先二分哈希求出它第一次跳 fail 的时间，和它的 fail \(v\)。除非它不需要跳 fail，此时它对答案数组贡献等差数列，否则它对答案数组的贡献为 \(v\) 对答案数组的贡献外加一段前缀加常数（跳 fail 之前有个深度差，跳 fail 之后都是一样的）。不会有深度问题吗？
[Hangzhou22L] Levenshtein Distance（编辑距离）
Levenshtein Distance - Problem - QOJ.ac
改为求 \(\min(k, \text{s与t的编辑距离})\)。\(k\leq 5000, |s|, |t|\leq 10^5\)。这是上世纪的论文题，听说甚至是 Tarjan 先生的。
显然
\[d_{i, j}=\min(d_{i-1,j-1}+[s_i\neq t_j], d_{i-1, j}+1, d_{i, j-1}+1) \]必然有
\[d_{i, j}\geq |i-j| \]根据归纳可以发现：
\[d_{i-1, j-1}\leq d_{i, j} \]即对角线单调不降，启发沿着对角线转移。
令 \(f_{v, t}\) 表示最大的 \(x\) 使得 \(i-j=t, d_{i, j}=v\)。转移考虑先走第二 / 三种转移，然后沿着对角线一路右上，走到了 \(f_{v+1, t\pm 1}\)。注意到后者是后缀数组问题，可以建立后缀数组以 \(O(1)\) 转移。因为状态数是 \(O(k^2)\) 的，所以总复杂度 \(O(k^2+n\log n)\)。
前缀本质不同子串个数（SAM）
建 SAM，\(i\) 从 \(1\) 枚举到 \(i\)，尝试求出增量，从 \(S[1,i]\) 往上跳，一边跳一边打标记，直到遇到打过标记的点停止。显然正确。
[NOI2018] 你的名字（SAM）
P4770 [NOI2018] 你的名字 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
全局的情况。可以将 \(T\) 在 \(S\) 的 SAM 上跑，对每个 \(r\) 求出最小的 \(l\) 使得 \(T[l,r]\in S\)。之后，对 \(T\) 建 SAM，将这些非法的 \(T[l,r]\) 标记出来，复杂度显然是 \(O(|T|)\)。
区间的情况。即我们只需要多次判断 \(S[l,r]\) 是否在 \(S[L,R]\) 中，即查询某个等价类中在某个值之后的最小的 endpos 是否 \(\leq\) 某个值。线段树合并即可。
[BJWC2018] Border 的四种求法（SAM）
P4482 [BJWC2018] Border 的四种求法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
即求一个最大的 \(x\)，\(S[l,x]=S[r-x+l,r]\implies LCS(S[1,x], S[1,r])\geq x-l+1\)。
建后缀树。从右往左扫，扫到 \(r\) 加入询问，扫到 \(x\) 尝试解决之前的问题。核心是重链剖分，将询问放在每条重链上等待解决，在跳到重链的那个点打上一些标记，可以发现 \(x\) 和 \(r\) 打的标记点总有一个是我们需要的 LCA。于是就是分讨谁是 LCA，在不等式上合并同类项，线段树维护。
结论：一个串的 border 可以被分为 \(O(\log n)\) 段等差数列。
区间本质不同子串个数（SAM）
P6292 区间本质不同子串个数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
从前缀本质不同子串个数出发。链上的子串，将其答案记在左端点上。我们现在想要加入一条链。发现长度连续，endpos 相同的子串，可以 \(O(1)\) 次线段树操作一次解决。我们想干的事情就是：
- 将这条链划分为很多段，每一段的上次出现右端点（记作 \(lst\)）相同；
- 整条链的 \(lst\) 推平为一个数。
将 \(lst\) 相同的段看作一条实链，这是 LCT 的 access 操作。\(O(n\log^2n)\)。
[ECFinal22B] Binary String
Binary String - Problem - QOJ.ac
划分为若干个 \(1\) 的连续段和 \(0\) 的连续段，每次操作就是 \(1\) 段右移，\(0\) 段左移，长度为 \(1\) 的段是反的。最终如果 \(0\) 比 \(1\) 多，会出现很多个 \(1\) 全部独立一段，然后出现循环。所以我们需要求出什么时候“会出现很多个 \(1\) 全部独立一段”，再求那个时候的循环节。可以找一个点断开，使得前缀和 \(\geq 0\)，后面怎么做不会。
[CCPCF22G] Recover the String
Recover the String - Problem - QOJ.ac
首先可以做拓扑排序，求出每个点代表的长度。从最长的串开始，发现如果有一个点只有一个出边，
标签：子串,Trie,SAM,leq,2024.8,ACAM,选讲,fail,字符串 From： https://www.cnblogs.com/caijianhong/p/18336620