AC 自动机 基本原理

还没写好，先别看！！

【算法学习笔记】06 AC自动机

fail：相当于 kmp 的 next

• 没有这个儿子就沿着 fail 往上跳（bfs 序：保证在此之前的已经连完了），O (串长总和)

• 按照Trie结点个数，去均摊：go[0-25]，下一个点是a-z会跳到哪里去

  go[u][i]=son[u][i], u有i这个儿子
  go[u][i]=go[fail[u]][i], u没有i这个儿子

  主席树维护go数组

build 步骤：

• 建 Trie

• 从根开始 bfs：有儿子则连儿子，否则连本身