冒泡ioa
冒泡ioa

[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])

代码

发表评论

textsms
account_circle
email

冒泡ioa

[HAOI2016]找相同字符(后缀数组)
题目链接 题解 最近学后缀数组学得有点晕,还是要多练啊。 题目就一句话:求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。 根据容斥原理,只要分别求出两个子串合并后…
扫描二维码继续阅读
2019-05-05