【洛谷4070】 [SDOI2016]生成魔咒（SAM） 传送门 洛谷 Solution 考虑要求的是什么，前缀的本质不同的字符串个数？ 如果只要求一个串那么显然答案是(sum_{i=1}^{tot}len[i]-len[fa[i]])（实际上这个并不显然，想一想为什么） 接着就是在线的啦，你可别忘了SAM本身就是在线算法，每一次算一个贡献就好了。 代码实现 代码戳这里