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. 暂无来源
作者

ce-amtic

发布于

2021-03-10

更新于

2021-03-10

许可协议

CC BY-NC-SA 4.0

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×