week4_AC自动机

类似于week2,3；
然后这一节题目说是Trie图，其实用AC自动机更容易搜出来结果。
对于一个M<=10^6的字符串；N个长度为L的单词；
最差的办法：
对于M枚举起始位，采用week2的trie树方案，尝试在单词trie树上走到某结点；
讲解比较细的版本：Trie图
过程和kmp非常类似。
kmp的过程是:如果匹配成功，那么向前平移对准，next[i]=j；
如果匹配失败，那么j=next[j],即调整到可能的匹配位置。
类似的，对于trie图：
如果匹配成功，向前移位；
如果匹配失败，那么将齐位校准到可能的匹配位。用来代替next数组寻找最长匹配(失败段的后缀，也就是新匹配的前缀)位置的，就是后缀指针。(hiho说是后缀，上文引用的blog说是前缀，随意啦)
看了看范叔叔和学弟的模板。。。压力很大啊。

过了好tm久翻到ac自动机才又想起来我这儿还有个这 额滴神啊。
赶紧解决掉。。。
捋一遍流程:
每个节点包括：
对应字符串；后缀指针指向的字符串；到达后缀节点后每条路径走出的字符串（包括父节点后缀指向得到的字符串，由bfs得出）；

初始化：根节点对应null；根节点及其子后缀指针也null；
然后建树，查找。嗯 我选择抄板子先。