AC自动机是个很神奇的数据结构。
这是一道模板题。
首先考虑将模式串们构成$trie$树。用$nxt_i^c$表示从$i$走$c$这个字母会走到的儿子，$S_i$表示从根走到$i$中间经过的边上的字母按顺序连接。
然后定义$fail_i$指向与$S_i$的后缀匹配的最深前缀$S_j$。
于是，可以考虑和KMP相似的方式来更新$fail$指针。
不同的是，这里是用上一层的$fail$指针来更新下一层的$fail$。
这样就可以用$bfs$更新了。
更新的时候用以下公式：$fail_{nxt_i^c}$设为$nxt_{fail_i}^c$。
然后还有一个优化：如果当前节点没有走$c$的儿子，那么就将$nxt_i^c$设为$nxt_{fail_i}^c$。
查询的时候现在在$u$节点，现在查询串的这一位为$c$直接向$nxt_u^c$走即可。
这个数据结构可以在题目为以下形式的时候使用：
给定$n$个串，要构造一个长度为$m$的串，其要满足每一个位都被给定的某个串覆盖/存在一个给定的串作为它的子串/其中出现的所有子串是给定的串的话都有一定的贡献/$\dots$，求构造串的种数/最大价值
然后使用的时候就当它是个$trie$就行了（其实$fail$数组在用的时候基本不会出现），只是走一条边后可能会删掉当前匹配到的一个前缀，跳到与其平齐或在其上方的节点。