主要思路
这也太他妈毒瘤了吧。
这个题首先肯定是要离线的，在线肯定没发做。事实上，我们可以对这个匹配分为三类：在上升链上、过 LCA 或者是在下降链上。这三者可以分开进行统计。上升链和下降链可以通过对询问字符串正反建 AC 自动机、然后在原树上做 DFS 即可；经过 LCA 的链有点难处理，发现能参与匹配的字符个数是与 \(|\text{询问串}|\) 相关的，所以我们把左右链的两个部分拼起来，然后单独跑 KMP 即可。
代码好长，狗屎一般。
Continue reading →Codeforces 1240D: Stack Exterminable Arrays 题解
主要思路
刚开始看到分治的标签就下定决心用分治做，没一会发现信息非常难利用就弃疗了。考虑用类似于 KMP 的 AC 自动机的方法完成本题。
首先设置\(dp[i]\)为以\(i\)开头向右延伸的答案，那么我们往左的时候可以合并之，并设置\(nxt[i]\)来进行跳跃；由于得到\(nxt\)数组的过程暴力做时间复杂度会 GG，所以我们可以使用类似 AC 自动机的方式用 Map 合并信息：交换\(nxt[i]+1\)位置的 Map 并设置当前位置。最后做 DP 即可。
P3346:「ZJOI2015」诸神眷顾的幻想乡 – 题解
主要思路
这算是广义后缀自动机的一个通用(general)运用。我们可以像统计多个串一样来做这个，只不过我们需要在树上 DFS 时记录分岔点的 SAM 节点，然后进行回溯。剩下计算本质不同字串个数的方法就很套路了。
后缀自动机 | SAM
概述
后缀自动机是处理字符串信息的有力工具。后缀自动机存储在 Trie 树上，配合 Link 指针就可以被认为是一张 DAG。任意一条从原点出发的路径都可以被认为是这个字符串的一个子串，且在后缀自动机上不会存在重复的子串信息（然而，我们可以进行一些扩展来维护子串位置信息）。
AC 自动机 | Aho-Corasick Automaton
「Fortuna OJ」Jul 8th – Group B 解题报告
今天这几题咋就那么毒瘤呢？
A – String
其实这道题考场上应该能做出来的，是一道很简单的计数问题。在考场上一看到字符串就懵了，不知道为什么我对字符串的字典序有阴影，现在看来就是一道傻逼题。
考虑这样计数：
- 枚举一个\(i\)，考虑前\(i-1\)个字符与\(T\)串相同，然后第\(i\)个字符小于\(T[i]\)，这样可以保证后面怎么放置字母都能满足要求。
- 在枚举了\(i\)的情况下，枚举字符\(ch\)，范围在\([a, T[i])\)，考虑以下两种情况对答案的贡献：
- 如果\(ch = S[i]\)，那么后面需要变动的字符个数为\(k\)个，对答案的贡献：\[ {n – i \choose k} 25^{k} \]
- 如果不等于，那么后面需要变动的字符个数为\(k-1\)个，因为本位占了一个；对答案的贡献：\[ {n – i \choose k – 1} 25^{k – 1} \]
- 贡献之后，如果本位\(T[i] \neq S[i]\)，那么把\(k–\)，代表多固定了一个不同的字符。