今天来小谈一下AC自动机的优化。
1：在 trie 树中被搜过的点不用再搜第二遍，标记一下，因为答案已经统计入答案中。
2：有点类似路径压缩的感觉。
1 if (int y=e[x].nxt[i]) 2 { 3 e[e[x].nxt[i]].fail=e[e[x].fail].nxt[i]; 4 q[++tail]=y; 5 } 6 else e[x].nxt[i]=e[e[x].fail].nxt[i];
如果 nxt 数组为空，则 假设个虚拟节点，然后将它连入下一个 fail 当中 。实现了路径压缩（因为之后如果 nxt 数组不为空，就不用判断节点是否为空，直接开做，因为连的 fail 一定是有值的）
这里还蛮像 并查集的路径压缩 的，觉得难理解的思考思考这个。
原文：https://www.cnblogs.com/Frank-King/p/9643314.html