BZOJ 3277 串 / BZOJ 3473 字符串

发布于 2018-01-05  146 次阅读


题目链接:

http://www.lydsy.com/JudgeOnline/problem.php?id=3277

http://www.lydsy.com/JudgeOnline/problem.php?id=3473

题意:给定 n 个字符串,询问每个字符串有多少子串(不包括空串)是所有 n 个字符串中至少 k 个字符串的子串?


直接对所有串建广义后缀自动机,如果你看了 clj 的 ppt 并且很熟悉那一套理论,一个状态 s 代表的串的种类数就是\(mx_s-mn_s+1\)。

这个怎么求呢,mx 可以直接处理出来,考虑到\(mn_s=mx_{fa_s}+1\),所以\(kind_s=mx_s-mx_{fa_s}\)

 


一个非常弱的准退役OIER