算法理解
即在字典树上跑kmp
T1:
根据这个结论我自己手搓了一个AC自动机上去，喜提TLE
我是如何操作的呢？
我当时的想法是这样的：我们把字典树从根到该节点形成的链看成是一个模式串与文本串进行匹配，然后就用一个dfs来传递j就可以解决了
然后我打开书一看到这幅图，立马就不淡定了
我dfs可能nxt数组并未 \(nxt[u]\) 在u之前更新到
所以我们只好采取bfs
然后洛谷上过了，ybt又TLE了
原因是我没有用一个小小的优化：
if(!tr[x][i]){
tr[x][i]=tr[nxt[x]][i];
continue;
}
如果这个地方本身就没有字符，那么意味着我们就要往前跳了，我们考虑正常的kmp跳法就是跳到有字符了为止，也就是说我们要跳的位置都是没有字符的，那我们就把这个位置修改为第一个有值的位置，下一次跳直接一步到位。
最后统计答案时直接就能访问到第一个合法状态，然后在暴力往上跳所有nxt然后统计有哪些被访问到了，因为跳一次nxt可能只是深度-1，所以因为题目中有限制字典树深度最多为50，所以复杂度为 \(O(M*50)\)
标签：nxt,AC,字符,题解,ybt2.5,tr,自动机,字典 From： https://www.cnblogs.com/zcxnb/p/18587218