Border Theory | 基本子串字典

· · 算法·理论

*本文为学习笔记。

证明：辗转相减法。若 p_1，p_2 是 s 的周期，不妨设 p_1\le p_2，则对于 1\leq i\leq p_1，i+p_2\leq|s|，故 s_i=s_{i+p_2}=s_{i+p_2-p_1}，s 的后半段也有相似结论，所以 p_2-p_1 是 s 的周期。

证明：对于 u 左端点于位置 i 在 w 中出现，不妨设 i+p_1、i+p_1+p_2 也作为左端点在 w 中出现（p_1,p_2\geq 1），由于 2|u|\geq|w|，所以三次出现的 u 必定有重合，所以 \gcd(p_1,p_2) 是 u 的周期，i+kp_0 也是 u 在 w 中出现的位置，所以 p_1=p_2=p_0。

所以如果两个串长度相差不大，会有很多非常好性质。

所以我们在处理 Border 问题时，可以使用 ST 表的思想，考察长度为 2^k 的子串，再处理一般子串。

引入基本子串字典：记 N_k(i) 为长度为 2^k 的以 i 开头的子串，将 N_k 按大小排序。空间与时间是 O(n\log n) 的。因为我们可以在倍增求后缀数组的过程中，自动把长度为 2^k 的子串排好序。

考虑如何处理区间 Border 问题，P4482 [BJWC2018] Border 的四种求法。

首先倍增分段，只考虑长度在 [2^k,2^{k+1}) 中的子串。考虑前、后缀四个长度为 2^k 的子串，从左到右依次为 u_0、u_1、v_1、v_0 如图。

考虑一个长度在 [2^k,2^{k+1}) 中的 Border t，t 的前缀与后缀长为 2^k 的 子串应为 u_0、v_0。则如图所示，u_0 应在子串 v_1v_0 中匹配，同理 v_0 应在子串 u_0u_1 中匹配。

我们可以用等差数列的引理，这个引理告诉我们，u_0 在后缀中的匹配是一个等差数列，v_0 在前缀中的匹配是一个等差数列，所以我们只需要求这两个等差数列的交集，就可以得到 Border，因为 Border 可以由 u_0、v_0 两段拼接起来得到。

两个等差数列求交当然也是等差数列，实际上我们得到了 Border 的另一条性质：长度在 [2^k,2^{k+1}) 中的 Border 构成等差数列，也就是说 w 的 Border 是由 \log |w| 个等差数列构成的。

如何对两个等差数列求交，不是非常容易，但我们试图证明，如果两个等差数列项数不小于 3，这两个等差数列公差相等。

证明：不妨设 u_0 的最小周期小于 v_0 的最小周期，考虑 u_0 在后缀中的匹配，u_0 在其中出现三次，则三次的偏移为 u_0 的最小周期 per(u_0)。考虑 v_0 这一段中现在有了两个周期，per(u_0) 以及 v_0 本身的周期 per(v_0)，又我们设 per(u_0)\leq per(v_0)，所以使用 Weak Perioud Lemma，\gcd(per(u_0),per(v_0)) 也为周期，所以只能 per(u_0)=per(v_0)。

现在问题转化为了求这个等差序列。

由于长度都是 2^k，我们就可以用到基本子串字典，等同于在 N_k 中查询一个长度为 2^k 的区间 (r-2^{k+1},r-2^k] 中有多少个满足 N_k(i)=N_k(l)（移植答案是个等差数列）。

确定最小值、次小值、最大值就可以得到一个等差数列。字典已经排序，可以二分求解，但是会多个 \log。

考虑以 2^k 为块长分块，查询时只需要查询相邻两块的等差数列拼起来即可，且公差相等，易于拼接。块内可以用哈希表维护，这样就是不带 \log 的。

所以我们就可以单 \log 解决区间 Border 问题。

【code】

咕咕咕（不敢写？）

比 Weak 难证多了。

证明：不妨设 p_1\geq p_2，设 g=\gcd(p_1,p_2)，总长度为 l。

考虑长度为 l-p_2 的前缀，可以用 Weak Perioud Lemma 相似的证明方法证出此段内 w_i=w_{i+p_1-p_2}。

使用数学归纳法：长度为 l-p_2 的前缀，有两个周期分别为 p_2 与 p_1-p_2，满足关系：p_2+(p_1-p_2)-g\leq l-p_2，是由 p_1+p_2\leq l+g 简单推导得到的。仍然满足命题条件，可以归纳，所以 g 是这个前缀的周期。

同理也可以得到 g 是相同后缀的周期。

两段可以拼起来的条件为前缀和后缀相交，即需要证明 p_2\leq l/2。因为 l\geq p_1+p_2-g\geq p_1+p_2-(p_1-p_2)=2p_2，所以得证。

问题：查询子串的最小后缀。

显然能用 SAM 做，但如果要求 O(1) 查询，如何做到？

把子串的后缀拓展成原串的后缀，求出沿伸到原串末尾的最小后缀，这个是可以用 ST 表的思想 O(1) 求出的。

这个有用吗，有点。如图，绿色部分为我们要求的答案，又因为红色为整个串在这个区间里的的最小后缀，所以绿色的串一定与红色的串长度为绿色串长度的前缀一样，否则红色就是更优的。

所以绿色串是红色串的 Border。而这个 Border 自然是越小越好，因为 Border 都是红色的前缀，越小的前缀排名越靠前。

形式化地，设 [l,r] 中的最小后缀为 w[p,|w|]，那么 w[l,r] 的最小后缀一定为 w[p,r] 的最短 Border。

这个如何求？我们不直接求。

我们有结论，一个串的最小 Border 一定不到长度的一半（因为由于 k 是周期则 2k 也是周期，所以最长周期不小于一半）！

我们做一件非常聪明的东西，将区间按 mid 折半，有 Minsuf(w[l,r])=\min(w[p,r],Minsuf(w[mid,r]))。

仿照 ST 表，令 k=\lfloor \log_2(r-l+1) \rfloor，那么 Minsuf(w[l,r])=\min(w[p,r],Minsuf(w[r-2^k+1,r]))。

和 ST 表一模一样，预处理所有长度为 2^k 的子串答案即可。

所以就可以实现 O(1) 查询了。

【code】

咕咕咕。