Border的四种求法

“我问你，border 有四种求法*，你知道么？”

*Border 的四种求法：指毛估，哈希，KMP 和 runs，其中最后一种求法极其罕见。

Peroid & Border

• （Border）我们定义串 $s$ 的一个非空严格前缀 $s[:k]$ 是 $s$ 的 border，当且仅当 $s[:k]=s[|s|-k+1:]$。注意这里 $k\in[1,|s|)$。

Border 具有一个优良的性质：$s$ 的一个前缀在 $s$ 中的全部出现位置，即是其在 $s$ 的失配树上的子树中的所有节点。而实际上，失配树上一个节点的祖先，即是这个节点的最长 border 所代指的前缀。

这样我们可以利用这个性质解决一系列单模式匹配问题，唯一的需求是快速建立失配树的结构。

这可以用 KMP 算法来解决：维护当前匹配的最长 border $p$，考虑扩展出一个字符 $c$ 之后，只需要验证 $p$ 到根的这一段路径上，有没有一个节点的下一个字符是 $c$。我们暴力跳失配树，容易发现每条树边只会被经过 $O(1)$ 次，因此总复杂度是均摊 $O(n)$。

注意这里的 border 针对的是同一个串而言，当然我们也可以在不同串之间定义 border，这就出现了 AC 自动机（多模式匹配）和 KMP 自动机（可回撤匹配）等一系列结构。

Border 在扩展 KMP 算法中还体现了另一个应用，因为不是特别有启发性所以这里跳过。

• （周期）我们定义一个整数 $r\in [1,|s|]$ 是串 $s$ 的周期，当且仅当 $\forall i\in[1,|s|-r]$，满足 $s[i]=s[i+r]$。我们称一个串所有周期中最小的那个为 $s$ 的最小周期，记作 $per(s)$。

接下来证明一个结论：“$s[:k]$ 是 $s$ 的 border”等价于“$|s|-k$ 是 $s$ 的周期”。

考虑先证充分性，可以发现 $2k\le |s|$ 的情况是 trivial 的。我们考虑 $2k > |s|$，此时设 $s=XA$，其中 $|A|=k$ 是 $s$ 的 border，可以发现 $X$ 必然是 $A$ 的严格前缀，那么去掉 $X$ 之后，可以转化为同样的问题，最后只会剩下 $X$ 的一段前缀。于是充分性得证，不难发现必要性也同理。

这意味着，一个串的所有周期和它的所有 border 是等价的集合。

关于周期，我们知道一些重要的结论：

• （Weak Periodicity Lemma）如果 $p,q$ 都是 $s$ 的周期，且满足 $p+q\le |s|$，那么 $(p,q)$ 也是 $s$ 的周期。
• （Periodicity Lemma）如果 $p,q$ 都是 $s$ 的周期，且满足 $p+q-(p,q)\le |s|$，那么 $(p,q)$ 也是 $s$ 的周期。

这意味这周期的出现是极其规律的。或者换个角度讲，border 的出现也是非常规律的！

可以发现如下规律：

• 对于串 $a,b$，满足 $2|a|\ge b$，则 $a$ 在 $b$ 中的匹配位置构成一个公差为 $per(a)$ 的等差数列。
• 对于串 $s$，$s$ 的所有长度大于等于 $\frac{|s|}{2}$ 的 border 构成一个等差数列。
• 对于串 $s$，$s$ 的所有 border 排序后形成 $\log |s|$ 段等差数列。

对于第一和第二个结论，可以通过 WPL 简单证明；而第三个结论只需再利用 “border 的 border 还是 border”这个性质即可证明。

Runs & Lyndon Factorize

我们考虑从另一个角度理解周期，引入 runs 的概念：

• （Runs）我们定义一个三元组 $(l,r,p)$ 是 $s$ 的一个 run，当且仅当 $per(s[l:r])=p$，且 $2p\le r-l+1$，且 $s[l:r]$ 是极长的一段最小周期为 $p$ 的串。特别的，实数 $\frac{r-l+1}{p}$ 称作一个 run 的指数。

可以发现这个东西和周期联系密切，它的本质即是对极长严格周期串（即满足 $2per(s)\le |s|$）按照它们的最小周期分类。

• （The Runs Theorem）记 $\rho(n)$ 表示长为 $n$ 的串至多含有的 run 的数量，$\sigma(n)$ 表示长为 $n$ 的串所有 run 的指数和的最大值，那么有 $\rho(n)<n,\sigma(n)\le 3n-3$。

这意味着我们可以求出一个串的所有 run，考虑怎么求。

• （Lyndon 串）设 $<_\iota$ 是比较运算符，其中 $\iota=0/1$，分别对应两种相反的比较，这里令 $<_0\Leftrightarrow<,<_1\Leftrightarrow >$。我们称 $s$ 是关于 $<_\iota$ 的 Lyndon 串，当且仅当 $\forall i\in [2,|s|]$，满足 $s<_\iota s[i:|s|]$。
• （Lyndon 分解）称 $a_1a_2…a_n=s$ 是 $s$ 关于 $<_\iota$ 的 Lyndon 分解，当且仅当所有 $a_i$ 均是关于 $<_\iota$ 的 Lyndon 串，且 $a_i\not<_\iota a_{i+1}$。可以证明，一个串的 Lyndon 分解存在且唯一。
• （Lyndon Root）称 $\lambda=s[l_\lambda:r_\lambda]$ 是一个 run $u=(l,r,p)$ 关于 $<_\iota$ 的 Lyndon Root，当且仅当 $[l_\lambda:r_\lambda]\subseteq [l,r]$，且 $\lambda$ 是一个 Lyndon 串。

考虑反过来求每个 Lyndon Root。

我们把串 Lyndon 分解，然后枚举一个 $i$，设 $ed[i]$ 是这一段 Lyndon 分解的边界，那么以 $i$ 开头的 Lyndon 子串的右端点不会超过 $ed[i]$，一段 Lyndon Root 也必然是 $s[i:ed[i]]$ 的子串。

我们从这里开始，二分哈希找到包含 $s[i:ed[i]]$ 的极长循环子串 $s[l:r]$。如果这段子串合法（满足 runs 的定义），那么就找到了一个 run。显然一个 $s[l:r]$ 可能被统计多次，我们应当取周期最小的那一次。

如果对 $\iota=0/1$ 均做一遍这样的操作，我们就可以得到所有的 run。

我们发现依赖 runs 具有的优良性质，可以解决一系列周期相关的问题以及 border 相关的问题。这种方法比 SAM 等常见处理办法更加简洁，在时间和空间上可以获得进一步的优化。

但是这也是有局限的，因为 runs 无法表出非严格周期串，否则复杂度就错了。

一道栗题

给定一个仅包含小写拉丁字母的字符串 $s$。有 $q$ 次询问，每次询问形如 $(l,r)$，表示询问 $s[l:r]$ 这一段子串是否可以被表示成 $s[l:r]=X^kX’$ 的形式，其中 $X$ 是任意字符串，$X’$ 是 $X$ 的可空前缀，$k\ge 2$。

对于每次询问，如果这样的 $X$ 存在，输出最短的 $X$ 的长度；否则，输出 $-1$。

全部数据满足 $|s|,q\le 10^6$，TL = 2s(-O2) / ML = 128Mb。

显然求 $per(s[l:r])$ 等价于求 $s[l:r]$ 的最长 border，直接 KMP 即可 $O(q|s|)$。

求出 $s$ 的 runs，那么每次询问相当于矩形取 $\min$，直接离线二维数点即可，复杂度 $O((|s|+q)\log |s|)$。

需要特别说明的是，如果没有 $k\ge 2$ 的限制，那么本题相当于「BJWC2018」Border 的四种求法，解法也不再这样简单。

参考

• 《The Runs Theorem and Lyndon Tree》杨骏昭、徐翊轩、陈孙立，WC2019 讲稿

相关题目：

1. 暂无来源