引入

给定字符串 $S$ 与模式串 $P$。问 $P$ 的最长的是 $S$ 的子串的前缀的长度。

我会暴力！

$O(nm)$，非常显然。不讲。

喜欢哈希的小朋友们你们好啊！

注意到答案具备单调性。于是我们使用二分，外加哈希来检验。

复杂度 $O(n\log m)$，其中 $n$ 是 $S$ 的长度，$m$ 是 $P$ 的长度。

已经很优秀了，但是还不够，毒瘤出题人出了 $n=m=3\times 10^7$ 的数据范围！

等价重写

Hash 的算法相当于二分匹配前缀长度，然后枚举前缀匹配起始点。

重写为另一种等价的形式：枚举前缀匹配的起始点，然后二分产生的匹配的长度。

现在，Hash 的问题在于每次重新二分一看就非常不优。

当然我不是让大家写分散层叠（分散层叠也完全用不上）。但是我们获得了一些优化的可能。

包的

假设现在我们在一个匹配起始点 $i$，有一个长度为 $l$ 的匹配（意味着匹配的结束点在 $e = i + l - 1$）。

考虑一个起始点在 $i$ 之后的匹配：假设起始点为 $j$。

有两种可能：

  1. $j \leq e$
  2. $j > e$

我们先处理所有第一种情况，然后我们重置 $i = e + 1$ 就可以继续处理第二种情况。

注意到第一种情况具备非常神奇的特性：$[j, i + l)$ 这段下标区间内 $S$ 的子串，等于 $P$ 长度为 $i + l - j$ 的前缀，而同时，当前起始点在 $i$ 的匹配中，与这部分对齐的一段后缀也等于这段子串！

（图示：）

1
2
3
4
5
6

      i                  j  e
S: ...[a  b  c  x  y  z  a  b]...
P:    [a  b  c  x  y  z  a  b] (长度为l=8)
P':                     [a  b  c  x  y  z  a  b]
                  公共段：|--|
       |--|（公共段在前缀的出现）

相当于，$P$ 的长度为 $l$ 的前缀有一个长度为 $i+l-j$ 的公共前后缀。

反过来，我们得到了一个第一类匹配存在的必要条件：

$P$ 的长度为 $l$ 的前缀有一个长度为 $i+l-j$ 的公共前后缀。

我们的目的是穷尽所有的前缀匹配（的开始位置）以计算最大前缀匹配长度。那么不妨在想象中将匹配开头升序排序。在找到一个可能开头 $i$ 之后，我们随即检查它后面的第一个的可能开头 $j$。

假设它是第一类的。如果不是，容易处理。

注意到 $j$ 最小意味着 $i+l-j$ 最大，也就是说这段公共前后缀的长度是最大的。

那么就引出了我们的主角：border（包的）——字符串最长公共严格前后缀。

注意：是“严格”的。因为整个前缀本身作为平凡公共前后缀会导致算出 $j=i$，即原地不动。

如何匹配？

非常简单。每次在位置 $i$ 找到一个匹配之后，直接跳到 border 位置（$e-\mathrm{border} + 1$）找下一个匹配，如此反复。

如果找不到（border 长度为 0），那么暴力指针加一，找下一个匹配。

注意到这一定是对的。因为我们每次都找“未处理集合中的第一个”。

如何预处理？

border 很好，怎么算？

我们需要计算模式串每个前缀的 border。那么不难想到每个前缀利用上一个前缀的结果。

对于长度为 $i+1$ 的前缀，假设它有一个公共前后缀，那么这个后缀必然包含 $i+1$。

注意到前缀去掉 $i+1$ 对应的字符的部分和后缀去掉 $i+1$ 得到的东西是相等的，这是长度为 $i$ 的前缀的一个公共前后缀。同样的，必须是严格的（因为我们要算出 $i+1$ 长度的前缀的 严格 公共前后缀）。

于是有重要结论：长度为 $i+1$ 的前缀的 border 长度最多是长度为 $i$ 的前缀的 border 的长度加一。

得到了这个约束之后，我们肯定想到枚举这个长度为 $i$ 的前缀的公共前后缀。并且由于要最大化长度，这个公共前后缀也越长越好。

那么我们肯定优先考虑 border。如果 border 不行怎么办呢？

答案是取 border 的 border。然后这个公共前后缀的 border……如此循环往复，直到没有 border（border 长度为 0）。

看起来似乎是一个贪心。为什么是对的？

因为这样可以取遍所有的公共前后缀。注意到对于两个不同长度的公共前后缀 $b, t$（$b$ 更长），$t$ 在前缀的那一段是 $b$ 的前缀，在后缀的那一段是 $b$ 的后缀，所以 $t$ 也是 $b$ 的公共前后缀。

所以除了 border 外的所有公共前后缀，都是 border 的公共前后缀，那么自然我们每次取“最长的”就能取遍所有。

复杂度？

看上去枚举所有公共前后缀简直暴力完了。复杂度凭什么是对的？

还是那句话。关键结论：

长度为 $i+1$ 的前缀的 border 长度最多是长度为 $i$ 的前缀的 border 的长度加一。

预计算阶段，我们每次计算一个新的前缀最多会回退旧前缀的 border 长度次。然后 border 长度减少至少这么多。

这里有点类似单调栈的复杂度分析：我们的每个新字符贡献 border 长度的一次增长，这次增长之后贡献常数大小的计算量。

匹配阶段，同理：每个主串中字符匹配时最多使得匹配前缀大小加一，而失配时回退不会超过当前前缀的大小次。均摊复杂度依然是对的。

所以总复杂度就是全线性。

小拓展

注意到这个东西能够自然拓展到全模式匹配上：只需要考虑前缀匹配的长度等于模式串长度的那些匹配就行了。