6816

· · 题解

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

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

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

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

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

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

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

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

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

考虑第三个条件，这时候是不是子串的长度越大越好呢？思考之后可以发现不一定，其与前缀的区别是超出部分仍然在 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 长度的一半，那么以下两个条件就不可能同时满足：

对于前一种情况，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 的性质。这种综合地观察性质，发现困难的问题的特殊性质，而非简单地套模板的思考过程是很有价值的。