自动搬运

查看原文

来自洛谷，原作者为

	dottle Cy@?g|^a

搬运于2025-08-24 22:24:16，当前版本为作者最后更新于2022-01-08 10:38:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

此题题面翻译有误，应还有一个限制： $s$ 是 $S$ 是子串。在你看到这道题之前题面可能已经被修改了。

考虑怎样的子串 $s$ 可以匹配原串，条件有三个：

1. 考虑子串在 $S$ 中的所有出现位置，两个位置的间距不应大于 $|s|$。
2. 设 $s$ 第一次出现的左端点为 $l$，则 $l$ 左侧的部分再加 $l$ 右侧的一部分应是 $s$ 的一个后缀。
3. 设 $s$ 最后一次出现的右端点为 $r$，则 $r$ 右侧的部分再加 $r$ 左侧的一部分应是 $s$ 的一个前缀。

后两个条件是类似的，但是后续的处理方法不太相同，因此拆开写。

首先考虑第一个条件，子串的出现位置这一问题引导我们想到 SAM，再加上“最大间距”这一条件，一个自然的想法是使用 SAM +线段树合并求出 $endpos$ 集合。线段树合并时，维护出此时所有间距中最大的一个。

依次考虑所有等价类，再考虑此等价类中有多少种符合题目条件的子串，我们就可以不重不漏地求出所有答案。现在我们考察 SAM 的一个节点，对于此节点对应的等价类，我们已经求出了以下信息：

• 首次出现的位置 $L$ 和末次出现的位置 $R$。
• 两次出现的最小间距 $x$。
• 此等价类对应的最小长度 $l_{min}$ 和最大长度 $l_{max}$。

接下来，将以样例中 $endpos=\{7,10\}$ （即 aabaa 所在的等价类）为例分析。

考虑第一个条件，则有约束：

• 此等价类中合法子串的长度至少为 $x$。

考虑第二个条件，我们会猜想，是不是子串的长度越大越好呢？确实如此，因为超出部分可以超过 $S$ 的开头，不会使匹配失效。也就是说，我们只需要求出这个长度的最小值。考虑我们用当前的子串的后缀尽可能地匹配一段前缀，设匹配到的前缀长度为 $a$，则应当有 $a\ge L-len$。例子中 $a=2$，$L=7$，若 $len<5$，则中间会空一段子串无法匹配。观察这个 $a$ 的定义，发现它其实是 $1\sim L$ 这段前缀的 border。因此：

• 此等价类中合法子串的长度至少为 $L-border_L$。

考虑第三个条件，这时候是不是子串的长度越大越好呢？思考之后可以发现不一定，其与前缀的区别是超出部分仍然在 $S$ 中，可能会使匹配失效。因此，我们需要单独研究怎样的串才是满足第三个条件的。

不妨将等价类中的某一个子串单独提出来，考虑如何判断它是否合法。例如现在考虑 $R=10,len=5$ 的子串，即判断 aabaa 能否匹配 aba，注意此时向前超出的部分也需要判断是否合法，所以我们可以把他们拼在一起，变成了 aabaaaba，这其实是一个原串的后缀。这时不妨倒过来思考，考虑对于一个后缀，在 $R$ 满足什么条件的时候，这个后缀才是合法的。用这个串来重新描述 $R$ 的合法条件：前缀 $R$ 在截去一段后缀后，等于一个后缀 $i\le R+1$。前缀截取掉后缀以后还是前缀，也就是说条件就变成了：一个前缀可以完全匹配一个后缀，这就是 border！那么我们猜想，当 $R\ge n- border_i$ （$border_i$ 代表 $i$ 这个后缀的 border）时，$i$ 这个后缀是合法的。但是这个猜想有一个自然的反例：若 $border_i$ 大于后缀 $i$ 长度的一半，那么这个结论是有问题的。例如对于后缀 aabaabaab，$R=3$ 并不合法。然而，此反例是不可能成立的。注意我们选取的 $R$ 是等价类中最后的位置，因此如果 $border_i$ 大于 $i$ 长度的一半，那么以下两个条件就不可能同时满足：

1. $R$ 在后缀 $i$ 的前一半。
2. $i\sim R$ 属于当前考虑的等价类。

对于前一种情况，$i$ 的计算不存在问题；对于后一种情况，$i$ 根本不会被计算到。因此，我们的猜想是可以用来计算的。

最后，我们把所有条件整合到一起：

1. 子串的长度有三个下界：SAM 中求出的下界；$L-border_L$；最大间距 $x$。
2. 子串的长度有一个上界：SAM 中求出的上界。
3. 子串的起始位置 $i$ 有限制：$R\ge n-border_i$。

现在，我们已经考虑好了所有的条件约束。现在可以开始设计代码实现了：

1. SAM + 线段树合并。需要求的东西上面已经列出。
2. 正串反串分别 KMP。正串用来求条件 $2$ 的约束，反串用来求条件 $3$ 的约束。
3. 考虑每一个等价类如何统计满足条件的点：这相当于是求一段区间中小于等于 $x$ 的元素的数量。可以离线树状数组，也可以在线主席树。

到此，我们就解决了问题的第一个部分。

接下来考虑第二部分，如何求出最短的解呢？

1. 考虑每一个等价类，相当于要求出一段区间内最后一个小于等于 $x$ 的元素的位置，这个也可以用主席树解决。
2. 若两个串长度相等，怎么比较它们的字典序？可以用 SA，也可以二分 + Hash 解决。

这样，我们就解决了这道题目。

总结一下这道题。首先考虑到用直观的语言描述题目的条件，然后尝试将其改写成容易约束的形式，最后再根据条件书写代码。其中的思考过程并非独立，大多都都是对题目性质的综合思考。例如第三个条件我们转化后的约束的正确性不仅来自 border 的性质，还来源于我们先前的 SAM 的性质。这种综合地观察性质，发现困难的问题的特殊性质，而非简单地套模板的思考过程是很有价值的。