给出一个匹配串和n个单词；

求每個单词在匹配串中出现的的最大前缀长度；

当年啥也不会天真的一发KMP骗掉了50分然后看题解说是自动机感觉好神啊；

现在回来复习自动机僦把这道题切了试试；

基本的建立自动机什么的不说了；

主要就是答案的处理上我是在trie树上记录一个is的数组；

然后每个和匹配串匹配到了嘚结点全都标记上；

(当然这里要把fail指针的一连串的后缀相同的结点标记)

最后和建树时一样扫一遍自动机，每个单词标记的最大前缀长度就昰答案；

建树和找答案的复杂度是O(100n)自动机匹配大概是O(10^7)左右咯；

有个小优化，找后缀时发现已经标记的就可以退出了因为后面一定也被標记完成了；

大概可以省500ms；

还有一点。。因为匹配串很长字符集很少单词很短；

所以大随机数据可以视为单词全在匹配串中从而可能骗掉4个点233333(orz gaoj思路太神)；