[算法] AC自动机

前言

自从考试考了一次AC自动机后, 我就上网找博客学习。 但许多博客并没有仔细讲解AC自动机中一个关键部分: Fail树的路径压缩。 有的只是放个图, 模拟下过程, 告诉你:“这是理所当然的”。 当然不能这样。 所以我, 本蒟蒻, 来分享一下自己的见解。

前置知识

AC自动机思想的基本理解。本篇只有精髓。

关键

if(Ch[u][i])
    Fail[Ch[u][i]] = Ch[Fail[u]][i];
else Ch[u][i] = Ch[Fail[u]][i];

这段话熟悉吧! 就是建立Fail树的核心语句。
我们在发现u之后失配, 就一直找Fail[u], 直到要么Ch[Fail[u]][i]有直或者我们到了根。 所以需要递归。 但未啥我代码里没有while之类的语句呢?
看好了:

Chu = Ch[Fail[u]][i];

这有点像并查集的路径压缩。 也许你会说“这不会违反Trie树的性质吗?” 没事的。

每次当我们发现结点u缺少通向i的子结点时, 我们将Fail[u]的儿子过继给u时, 同理如果Fail[u]没有通向i的子结点时, 他也会过继Fail[Fail[u]]的儿子, 直到有儿子为止。 所以我们不用递归了。 与并查集中Fa[x] = Find(Fa[x])异曲同工。

后记

谢谢浏览

Last modification:August 25th, 2019 at 04:25 pm

3 comments

  1. Garbage

    Rathen%%%

  2. marTixx

    %%%Rothen

  3. Illusions

    orz

Leave a Comment Cancel reply