题意

对于一个字符串 \(s\) 的子串 \(s’\) , \(f(s’)\) 的值就是把 \(s\) 中所有的 \(s’\)  完整出现过的位置中 \(s’\) 的每一个字符出现过的位置全部拿出来,所得到的线段条数。

求满足 \(f(s’)=k\) 的 \(s’\) 个数。

分析

\(f(s’)\) 就是把 \(s’\) 出现过的位置的集合拿出来,如果相邻两个位置之差不超过 \(|s’|\) \(+1\) 。

于是我们用 SAM 跑出 endpos 集合,然后想办法维护相邻元素的差。

满足 \(f(s’)=k\) ,一定是 endpos 集合中第 \(k\) 大元素满足大于 \(|s’|\) ,因为这样的话,可以保证出现的位置中一定有至少 \(k\) 个重合,如果有 \(k+1\) 大,还需要满足第 \(k+1\) 大的间隔小于等于 \(|s’|\) 。

考虑用主席树维护间隔。

SAM 跑出后缀树以后,按照 dfs 序编号,然后自底向上维护 endpos 集合。 endpos 集合需要启发式合并,每次插入一个新的元素,维护插入新元素以后所产生新的间距,在主席树上修改就好了。

主席树内存需要比较大,但开的太大程序又跑得慢,需要卡一卡。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注