做大数据和网站开发的前景,中山网站建设工作室,网站的前端用什么语言,专业企业网站建设公司比我小一届却吊打我的大脚玩家(djwj233)的博客 什么是 AC 自动机 AC 自动机是一种多模匹配算法#xff0c;就是解决 多个模式串 匹配 单个/多个 文本串用的。 AC 自动机的过程 P3808 【模板】AC 自动机(简单版) 总的来说#xff0c;AC 自动机类似将所有串跑一个 KMP。 看到有… 比我小一届却吊打我的大脚玩家(djwj233)的博客 什么是 AC 自动机 AC 自动机是一种多模匹配算法就是解决 多个模式串 匹配 单个/多个 文本串用的。 AC 自动机的过程 P3808 【模板】AC 自动机(简单版) 总的来说AC 自动机类似将所有串跑一个 KMP。 看到有很多个模式串自然想到建一棵 Trie 树那么建了 Trie 树之后我们就从头开始尽可能地向下走。 要是往下匹配走到头了怎么办呢我们考虑借用一个 KMP 的思想从当前节点跳到它的最长的在 Trie 中的真后缀这样就可以继续匹配了。 具体地我们对每个结点定义一个 \(\text{fail}\) 指针指到当前结点最长的在 Trie 中的真后缀。 那么怎么求出这个 \(\text{fail}\) 指针呢只需要和 KMP 一样不停地向前跳就可以了这样就在 \(\mathcal O(\sum|s_i|)\) 的时间内完成了建树。 实现的时候用一个 bfs 的过程完成。 $\texttt{code}$ void get_fail()
{queueint q;for(int i0;i26;i) if(ch[root][i])Fail[ch[root][i]]root,q.push(ch[root][i]);while(!q.empty()){int curq.front(); q.pop();for(int i0;i26;i){if(ch[cur][i]) q.push(ch[cur][i]),Fail[ch[cur][i]]ch[Fail[cur]][i];else ch[cur][i]ch[Fail[cur]][i];}}
} 可以发现我们把 \(\text{fail}\) 指针直接并在了原先的 Trie 中这样形成的一个数据结构叫作字典图。
