SSOJ2762单词
1591+
作者：crxis 发布：2020-12-29 分类：AC自动机
题目大意：已知文章由n个单词组成，请问这些单词分别在文章中出现了多少次？
题目描述
原题来自：TJOI 2013
某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。
输入
第一个一个整数 N，表示有多少个单词，接下来 N 行每行一个单词。
输出
输出 N 个整数，第 i 行的数字表示第 i 个单词在文章中出现了多少次。
提示
样例输入
3
a
aa
aaa样例输出
6
3
1对于全部数据，1≤N≤200，所有单词长度的和不超过 106，保证每个单词由小写字母组成。
解题思路
在AC自动机模板上做简单修改即可。
首先，打好AC自动机模板，在匹配的过程中，发现文章由单词n个单词组成，其实匹配移动的过程，就是Trie树的建立过程，因为单词之间是断开的，所以最远走到的位置，就是他在Trie树上的位置，所以代码第14行就是记录根到p节点的匹配次数加1。
接着处理包含关系，如果每次都暴力往前一个短一点的前缀更新，容易超时，我们可以利用广搜队列逆序，自下而上更新，即可统计出每个前缀被匹配的次数。
最后输出的时候，因为单词可能重复出现，所以不能计每个节点对应哪个单词的结束，而应记录每个单词的结束位置，输出时输出该位置的匹配数量即可。
程序实现
