Y252 单词频率
题目大意
给定 \(n\) 个单词,求每个单词作为子串在所有单词中一共出现过多少次。
首先我们注意到,字符串 \(s\) 是另一个字符串 \(t\) 的子串等价于 \(s\) 是 \(t\) 的一个前缀的后缀。并且 \(s\) 唯一对应该前缀和后缀。
我们先通过字典树求出每个字符串是多少个字符串的前缀,记数量为 \(cnt_i\),则该字符串就会对其所有后缀产生 \(cnt_i\) 的贡献。
对其所有后缀的贡献,我们考虑在AC自动机预处理时记录所有节点访问的顺序(也就是bfs序),接着按 bfs 序反着计算i
对fail[i]
的贡献,这和拓扑排序是等价的。