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