欢迎来看 “片” （的简介）

由于-\(看片\)-生涯转瞬即逝，于是我选择对“\(片\)”进行一定的总结：

相信你一定看懂了

由于开始的时间有一点晚，就姑且认为我以后会慢慢补充吧......

字典树 Trie \(P8306\) \(【模板】\) \(字典树\)

解：字典树
要不是因为颓废，我早就把这个过了
非常简单，就是不停的向下建树，时间复杂度就是 \(string\) 的所有长度
那 \(3\times 10^6\) 是不是给少了？

\(P4036\) \([JSOI2008]\) \(火星人\) \((歪)\)

解：字符串，平衡树，(暴力

为什么要看题解呢？因为有些时候你可以大幅度偷工减料
看着好像是紫题，但却是橙题，直接暴力枚举，但 \(I\) 操作要用一下 \(String\) 的 \(Insert\) 操作，注意字符串的插入也只能插入 \(string\) 型。
至于它实际上想让我写的，可能 “未来” 某一天等我看懂平衡树会写出来吧，姑且认为那一天遥遥无期

AC 自动机 Aho-Corasick automaton \(P3808\) \(AC\) \(自动机\)

解: AC 自动机

首先，你要掌握字典树，大致了解一下 \(KMP\) 的思路，就是不回溯，然后你可以一步步做接下来的题目。

这个是模板模板题。

\(AC\) 自动机就是在字典树的基础上加入 \(Fail\) 数组，用来辅助你不直接跳到根节点重新搜索， 在整个过程中，加入操作与字典树建树完全一致，唯一不同的就是加入了 \(getfail\) 操作，来帮助后面你查询， 这个操作就是记录到父亲结点的 \(fail\) 并在将 \(fail_u\) 赋值为 \(fail_{fath}\) 的节点儿子中对应的同元素的节点，具体实现用 \(bfs\)。

整个“树”就会进化成这样：

绿边连向的点就是 \(fail\) 数组种的元素

(RT 被van了

查询就非常轻松了，由于赋值 \(fail\) 时是用父亲的元素进行的，所以可以保证不会有中间某一个元素不是我们查询串的元素的情况，所以每次加上对应 \(fail\) 的 \(cnt\) 值，在结束当前的字符串之后继续依照 \(fail\) 跳到下一个可以被查询的字符串中。

打完模板之后，再大另外几个模板:

\(P3796\) \(AC\) \(自动机\) $（简单版 $ \(II）\)

解：
在原本的模板基础上，去除查询中的 \(cnt\) 的赋为 \(-1\) 的操作，于是就可以算出每一个东西的具体出现此时，而后，排序，输出即可，注意没有 \(SPJ\) 要按照输入顺序输出。

\(P5357\) \(【模板】\) \(AC\) \(自动机\)

解：
可以发现，在 \(trie\) 上跑不停地向前非常恶心，不妨给它压缩一下，什么意思呢？ 拓扑排序，这样的话，就是从头往下不断的加上价值，在此之前，现将 \(S\) 的贡献加上去，后面拓扑把价值加上然后再后续输出的时候依据之前记录的地址输出即可（感觉讲了个寂寞，不讲了，看代码吧，dsc教的

想了一会，还是强行说一下吧，拓扑排序就是先把没有依赖的点的贡献加上，再不断地向后继中出自己外没有依赖的点前进，又因为整个图上不存在我是你的 \(fail\), 你又是我的 \(fail\) 的关系，即整个 \(fail\) 形成的形状是一个 \(DAG\) 因此，首先运用拓扑排序是不会有意义上的问题的，其次，正如上面所说的先后关系，对图进行拓扑排序求得的答案首先不会出现矛盾，其次也不会出现错误，为什么呢？ (不知道，性感理解一下，你看没有矛盾不就是不会有错误，是正确的了吗？

它优化了什么呢？
最片面的来看，在 模板二 中，\(getans\) 函数是有两次循环的，这样你就发现这一个模板所做的事情了，实际上就是先把最后输入的 \(S\) 串的贡献县加在路径上，然后用拓扑排序的形式将答案往下传，于是就从 \(\mathcal{O}(nm)\) 降到了 \(\mathcal{O}(n+m)\) (感觉很傻是吧，是不是感觉肯定有其他算法可以代替它

欸，下面是拓扑的时候都入队节点顺序，\(\textcolor{purple}{紫}\) -> \(\textcolor{#FFD700}{黄}\) -> \(\textcolor{orange}{橙}\) -> \(\textcolor{blue}{蓝}\) , 可以发现，最开始将 \(S\) 串放进来没有任何影响，一个个拓扑是没有问题的 (就当作是在瞎扯吧

左上角是S的名称，图里没什么用，请忽略