跳转至

Y252 单词频率

题目大意

给定 \(n\) 个单词,求每个单词作为子串在所有单词中一共出现过多少次。

首先我们注意到,字符串 \(s\) 是另一个字符串 \(t\) 的子串等价于 \(s\)\(t\) 的一个前缀的后缀。并且 \(s\) 唯一对应该前缀和后缀。

我们先通过字典树求出每个字符串是多少个字符串的前缀,记数量为 \(cnt_i\),则该字符串就会对其所有后缀产生 \(cnt_i\) 的贡献

对其所有后缀的贡献,我们考虑在AC自动机预处理时记录所有节点访问的顺序(也就是bfs序),接着按 bfs 序反着计算ifail[i]的贡献,这和拓扑排序是等价的。