BZOJ 3277 串 / BZOJ 3473 字符串


题目链接:

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}\)

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3277 串 / BZOJ 3473 字符串


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,