\(tr[i].end\) 为 \(1\) 时表示为该节点为串尾。
\(tr[i].sum\) 表示以该点为串尾的字符串数。
普通自动机
考虑对模式串建出自动机，在串尾打 tag ，在文本串上跑自动机，开一个栈维护当前位跑到自动机上的节点编号，一个栈维护剩余的字符，当跑到串尾时，弹出该串所有的字符，挂在自动机上的指针回退到该串入栈之前。
对 fail 树的操作 + DS 维护
考虑建出该字典图的 fail 树，考虑 fail 树的性质。由于串长不超过 \(20\)， 在每一个节点维护一个状压集合 \(S\) 表示从根到该节点的所有串能匹配的长度，考虑边 \(u->v\)，下传时显然有 \(S_v~|=S_u\)，特殊的，若该节点本身是串尾，则 \(S_u~|=(1<<dep_u)\) 。
考虑依旧使用状压来匹配，在字典树上跑当前的文本串，记录跑到的节点到根节点中的串尾的长度，也能用状压维护，最后把两个值与起来不为 \(0\) 就能计入答案了。
首先将病毒代码段插入自动机，建出 fail 指针，显然如果能在不走串尾的情况下在字典图上经过一个环则有解，这一过程可以通过 dfs 实现。
考虑一个自动机常见优化，当一个节点的 fail 指针如果指向串尾，则其一定不能走。
考虑自动机的匹配问题，可以枚举匹配到的文本串末端，求出其在自动机上的节点编号后在 fail 树上用 DS 维护，由于 fail 树上根到节点路径上所有字符串都为枚举字符串的后缀，所以不重不漏。
考虑本题，建出自动机后，建出 fail 树，由于 fail 树上 \(u->v\) 路径表示 \(u\) 的字符串为 \(v\) 的字符串的后缀，说明新增一个模式串，在 fail 树上以其为根的子树一定能新增贡献，删除同理。查询只需要像上文一样，枚举末端，然后单点查询就可以了。
于是只需要用 \(dfs\) 序转序列问题后维护一个支持单点查询，区间修改的数据结构即可。
套路的建出 fail 树，由于修改权值，我们不能将 fail 树上以其为根的子树全部修改，因为其他串可以被权值更大的子串所覆盖，所以我们考虑转成单点修改权值。
查询的话同理，我们枚举末端，求出节点编号为 \(u\)，考虑到根到 \(u\) 上的路径全为子串，我们只需要求路径最值即可，可以用树剖来维护。
自动机 + DP
在自动机上的 DP 十分套路，一般设 \(dp[i][j]\) 表示跑到自动机上的节点 \(i\)，并且当前匹配到文本串第 \(j\) 位的答案。
正难则反，考虑完全不可读的文章数，则答案为 \(26^m-ans~\)。
有一个显然的结论是匹配到的点能计入答案当且仅当其不是串尾，于是可以直接用来做转移的条件。
记 \(dp[u][j]\) 表示跑到自动机第 \(u\) 个点，匹配到第 \(j\) 位的方案数。
初始值 \(dp[0][0]=1\)
当转移后的节点不为串尾时有转移方程 \(dp[tr[u].ch[i]][j+1]+=dp[u][j]\) 。
P3041 [USACO12JAN]Video Game G
套路的，我们设 \(dp[u][j]\) 表示跑到自动机第 \(u\) 个点，匹配到第 \(j\) 位的方案数。
特殊的，我们在求 fail 指针时，以 \(u\) 为结尾的贡献要加上 \(tr[u].fail\) 的贡献，因为根到 \(fail\) 的路径组成的字符串为根到 \(u\) 路径组成字符串的一个后缀，当加入节点 \(u\) 时，后缀同样能累计贡献。
初始值 \(dp[u][j]=-INF\)
转移方程会比较简单：
\(dp[tr[u].ch[i]][j+1]=\max(dp[tr[u].ch[i]][j+1],dp[u][j]+tr[tr[u].ch[i]].sum)\)
标签：AC,匹配,tr,fail,自动机,节点,dp From： https://www.cnblogs.com/tidongCrazy/p/16867021.html