首先我们发现这题是一道裸的Aho-Corasick自动机。

经典做法是对于每个节点维护一个集合，记录走到这个点的时候将有哪些模式串的答案被更新。同时根据AC自动机的特性，更新节点u的同时还要更新节点fail[u]。这种做法能勉强通过40%的数据。

事实上，对于每个节点，我们可以只记录一个布尔值vis，代表该节点是否在匹配过程中被访问过，访问节点u时仍然需要递归地去访问fail[u]。可以保证每个节点至多被访问1次。与此同时，每次的insert过程中，我们记录：对于字符串i，匹配到长度j的节点编号match[i][j]。接下来对于每个字符串，我们在[0, 100]进行二分查找，每次检查vis[match[i][mid]]是否为真。总的时间复杂度是O(M|S|+N+Mlog100)，可以承受。

这时候其实还有一个小小的优化……
我们自行生成一个N=10^6的随机数据，会发现对于（几乎）所有的模式串，答案都等于该模式串的长度。由于字符集很小，我们可以认为，对于一个随机的数据，当母串足够长时，所有的模式串几乎都能在母串中找到匹配。故此，当N>10^6时，我采取了这样的策略：对于每个模式串，直接输出它的长度。

……然后就过了……最大数据280ms……23333333

后缀自动机裸题，但注意只匹配文字的前缀，不用再往pre上转移
由于n很大，数组开不出来，需要采用楼下神犇的方法过最后一个点Orz
http://blog.leanote.com/post/okami/vijos