夢に僕らで帆を張って
来るべき日のために夜を超え

标签 AC自动机 下的文章

October 31, 2019

洛谷P3966/TJOI2013 单词

题意给出$n$个单词,求每个单词共出现几次数据范围:单词总长度$\le 10^6$题解多模匹配,使用$\text{AC}$自动机解决需要注意的是,可能出现重复的单词;为避免字典树的值被覆盖,只记录第一个编号,而将其他相同的单词指向这个编号统计答案时,在该前缀的所有后缀上($\text{Fail}$树上的祖先节点上),将其自身答案累加上去,就是总共出现的次数代码:#include<ios...