日记

人类补完计划。

L 语言# Link to

设 $dp_i$ 表示文本串到 $i$ 的前缀能否被理解。对于字典树上的每个点 $rt$，记录一个 $len_{rt}$，表示 $rt$ 这个点表示的模式串的长度，如果它不是一个模式串就是 $0$。

我们跳 $fail$，设当前跳到了 $j$，如果 $dp_{i - len_j}$ 为 $1$，就说明 $dp_{i}$ 也是可行的。但是我们需要一点神秘小优化：

• 当 $dp_i$ 为 $1$ 时就不再跳了。
• 设当前答案为 $ans$，最长的模式串长 $maxl$，如果 $ans + maxl < i$，那么就说明 $i$ 和之后的都不可能是答案了。于是我们就可以 break 了。
• 常数优化，比如把结构体换成几个数组。

阿狸的打字机# Link to

文本串太多怎么办？直接可持久化。对于我们建出 $fail$ 树。然后处理出 dfs 序。遍历字典树上每个点 $u$。设 $u$ 在字典树上的父亲是 $fa$，那么 $u$ 对应的那颗树就是 $fa$ 的那颗树在 $dfn_u$ 的位置上 $+1$。查询的时候，直接在 $y$ 对应的那颗线段树上查询子树和（区间和）。

玄武密码# Link to

最烦小作文题面了。

我们对于字典树上每个点 $rt$ 记录一个 $vis_{rt}$ 表示 $rt$ 表示的串能否被文本串匹配。每次暴力跳 $fail$ 更新 $vis$ 就行。如果跳到了 $0$ 或者 $vis$ 为 $1$ 的点，那么就不用再跳了。

Death DBMS# Link to

AC 自动机 + 树剖 + 线段树板子题。

但是卡了我一个晚上，死因是 0-index。

我还是换成 1-index 吧。

后日谈 # Link to 后日谈

• 封闭内心：情绪影响 $-80\%$，专注度 $+60\%$，人际关系 $-20\%$， 决心 $\to \text{unknown}$，麻木度 $+ 200\%$。
• 开放内心：情绪影响 $+50\%$，专注度 $-20\%$，人际关系 $+50\%$，决心 $- 20\%$，麻木度 $\to 0$。

问：哪种最优？

我不知道。

我该开放心之壁，还是继续封闭内心，隔绝情感？

回答我！

是你自己要选择的这条路对吧？

你愿意接受这条路的结果吗？无论它如何？

我。。。愿意。

为啥要猜忌一些无谓的未来呢？

回答我！

4 月 25 日 # Link to 4 月 25 日

回答我。

e-Government# Link to

建出 $fail$ 树，当我们在字典树上查询文本串时，当前点 $rt$ 到 $0$ 在 $fail$ 树上的路径上的点都代表模式串的一次全新出现。那么这个问题就变成了一个单点修改，链上查询问题。把每次的单点更新影响扩大到整个子树，那么就变成了一个区间修改，单点查询的问题，直接上树状数组维护。

You Are Given Some Strings…# Link to

对于文本串和每个模式串，正着建一个 ACAM，把它们 reverse 一下再建一个 ACAM，然后记录文本串的每个前缀的后缀被模式串匹配了多少次，最后枚举分界点就行了。

后日谈 # Link to 后日谈

没啥可谈的。