题解：P11901 数组的划分

HJY2022 · 2025-05-27 09:31:33 · 题解

口胡一个不需要数据随机的做法，代码之后补（不是）。

假设我们已经转化到了 [HNOI2010] 弹飞绵羊 ，也就是说我们只需要能快速查询对于 t 的某一个区间的子串是不是给定的模式串的子串即可（更确切的说法是最长的能和某一个子串匹配上的区间的前缀）。在数据随机时可以说明长度不会大于 50，将所有长度小于等于 50 的子串加入一个哈希表中即可。不过在数据不随机的时候可能没有这个性质。

不过没关系，我们可以使用无敌的后缀自动机。由于后缀自动机中的一条路径代表原字符串的一个子串，因此我们相当于要判断某条路径与后缀自动机所有路径的 LCP，做法就是直接 DAG链剖分即可。每次判断重链上能不能匹完，轻链就暴力匹，匹不完的最后一条重链可以哈希+二分，总复杂度不变。