背景

为了解决字符串问题而出来的数据结构

前置芝士

Trie

就是通过树这种树形结构，充分利用LCP的树形结构

举个栗子：

我们有字符串:

abd

abe

ab

ba

他们的Trie长成这样

KMP

简单一句话而言：继承革命烈火！

为何如此而言？

对于文本串，我们假设当前的元素为\(i\)

对于模式串，我们假设当前的元素为\(j\)

我们要考虑的其实就是\(c_i\)与\(s_j\)不相同

如果不相同，我们就要返回去从\(i-j+2\)开始匹配

但是，我们都已经虽然\(c_i\neq s_j\)，但是我们可以之前是匹配的啊

所以，我们可以不用退这么多

我们只需要知道当前的最长后缀与最长的哪一个前缀是一样的，再将\(j\)指过来就行了

乍一看时间复杂度好像没变

但是巨佬们说这样的方法均摊是\(O(n)\)

还是不懂？

机房巨佬PPL的博客

# 做什么

给定n个模式串，求有多少个模式串在文本串中出现过

思路

预处理

将模式串建成Trie

主要想法

借用KMP的思想，我们每一次的匹配尽量使用已经有的最长前缀

fail指针

做什么

如果\(fail_i==j\)

那么\(root\)到\(j\)的字符串是\(root\)到\(i\)的字符串的一个后缀

所以你明白了吧，通过这个fail，我们可以每次不从根节点开始比较，这大大减少了时间复杂度

怎样求

也许你感觉这个fail数组一听起来就非常的难求，但是，出乎意料，他很好求

首先一点，\(dep_{fail_i}< dep_i\)，这通过fail的定义就能容易的知道

第一层的fail一定是根节点，这就是初始化

我们考虑一个点u和u的父亲fa

如果\(fail_{fa}\)和\(u\)的儿子都为v的，那么\(fail_u=v\)

如果不行呢？

继续跳不就完了？

代码

咕咕咕

查询

思路

很明显，有了fail数组之后，我们用fail数组在树上反复跳跃就行了

代码

咕咕咕

芝士：AC自动机

原文：https://www.cnblogs.com/loney-s/p/12220679.html