你好，我是 zbl2012 👋

AC自动机是一种基于 Trie树 与 KMP 的解决多模式串匹配问题的算法。其实本质上是在 Trie 上跑 KMP。 先把每个每个模式串建到字典树上，然后手动去模拟一下匹配的过程。发现，当匹配一个串时，如果匹配失败，就做一个类似 KMP 要跳到另一个地方重新匹配，我们要求解的就是要跳到哪里。 定义 faili 表示 i 这个点失配后应该跳到的点的编号，Ti 表示 Trie 上编号为 i...

字典树是我感觉为数不多的懂算法比写代码简单的东西了。 字典树是解决多组字符串匹配的问题的数据结构。 过程类似查字典，是先找每个单词的首字母，在找第二个，以此类推。 在建树的过程中，每一个单词，先遍历这个单词，把这个单词放到树上，就是一个如果它的首字母有，就向下看有没有第二个，以此类推，如果有，就新建节点。 值得注意的是，在建树的过程中，每一个单词的结尾都要打上标记，这样才可以统...

KMP 算法是解决一个串在另一个串中的匹配问题的算法。 如果给定两个串，让你求第二个在第一个中出现的位置。设第一个串是 s，第二个是 t，长度分别是 n 和 m。 首先可以想到暴力匹配，直接扫过去，如果不匹配就跳过，理想时间复杂度是 On，但是如果构造一个每一位都匹配的数据，就会被卡成 Onm。 发现暴力中，失配了就直接跳到开头，这样前面的查找就归零了，效率底下。 KMP ...

字符串hash是一种高效查询类似子串判重的问题的东西。 当每次我们想比较两个字符串子串是否相同时，一般情况下，要暴力匹配，时间复杂度最坏 On。 这时，字符串hash就有作用了。 字符串hash的原理就是给每一个串赋予一个哈希值，同过比较哈希值，就可以实现 O1 对比。 现在的问题就是：怎么实现这个哈希值？ 设有一个进制 B，则一个字符串 s 的哈希值为： \sum{i=1...