2026-07-22
Border
Range border query / Substring Dictionary
Border 理论告诉我们，长 \(|S|\) 的字符串的 border 可以被表示成 \(\log |S|\) 个等差数列. 我们希望建立一个数据结构来使得我们能够快速表达这件事情.
在介绍问题的解法之前，我们先看关于子串的一些等差数列性质：
对于串 \(u,w\)，若 \(2|u|\ge w\)，则 \(u\) 在 \(w\) 中出现的位置的左端点构成等差数列
Proof：对于三次相邻的出现 \(l,l+a,l+a+b\)，我们知道 \(a\) 和 \(b\) 都是 \(u\) 的周期；由于 \(a+b\le |u|\)，所以 \(\gcd(a,b)\) 也是 \(u\) 的周期. 若 \(a\neq b\)，则意味着存在更近的相邻出现，矛盾.
推论：在上述情况下，若出现了至少三次，则等差数列的公差等于最小周期.
基本子串字典：
考虑 \(w\) 的所有长度为 \(2^k\) 的子串，并对他们按照字典序排序，其中 \(N_k(i)\) 代表了 \(w[i,i+2^k-1]\) 的字典序. \(N_k\) 构成了字符串的基本子串字典.
对于区间 \([l,r]\)，考虑 \(u=w[l,l+2^{k+1}-1]\)，\(u_0=w[l,l+2^k-1]\)，\(v=w[r-2^{k+1}+1,r]\)，\(v_0=w[r-2^k+1,r]\).
令 \(u_0\) 在 \(v\) 中出现位置为 \(S_1\)，\(v_0\) 在 \(u\) 中出现位置集合为 \(S_2\)，手动模拟一下即刻知道 \(S_1\cap S_2\) 即为 Border 集合.
之前那个性质告诉我们，\(S_1,S_2\) 都是等差数列. 实际上，若 \(|S_1|,|S_2|>2\) 则还满足公差相等（由推论知道公差就是最小周期）.
Proof：不妨 \(d_2<d_1\)，则考虑 \(v\) 中出现的最后一次 \(u_0\)，其与 \(v_0\) 的交为 \(x\)；则 \(x\) 又有周期 \(d_1\) 和周期 \(d_2\)，且 \(|x|\ge 2d_1\ge d_1+d_2\) 故有更小周期 \(\gcd(d_1,d_2)\).
于是直接简单求交即可.