[HAOI2016]找相同字符(后缀数组)

题目链接

题解

最近学后缀数组学得有点晕,还是要多练啊。
题目就一句话:求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。

根据容斥原理,只要分别求出两个子串合并后的答案和两个子串单独的答案,最后的答案就是它们相减。

问题的关键就是如何在可以接受的复杂度内求这个答案。(我一开始连这个答案是什么都不知道)
实际上我们要求的是所有子串的lcp的和,可以把它想象成一个枚举起点,长度就是贡献的过程。

至于怎么求,其实首先要知道任意两个子串的lcp为它们之间Height数组的最小值,这样用ST表 $O(1)$ 查询可以使得整体复杂度达到 $O(n^2)$

但这还不够,我们发现,随着枚举的子串字典序增大,Height数组的最小值只会越来越小,于是我们可以用单调栈来维护。

具体来说,我们设 $f[i]$ 为字典序为 $i$ 的字符串和它之前的字符串产生的贡献,如果它的Height是当前最小的,则 $f[i]$ 为 $Height[i]\times (i-1)$ 而如果不是最小的,那就是上一个比它小的贡献+ $Height[i]\times (i-sk[top])$

代码

点赞

发表评论

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