Border 理论

chenxinyang2006 · 2022-09-19 18:52:21 · 个人记录

我曾经觉得，会了 SAM 就可以解决字符串大多数问题了，但并不是。

字符串长度记为 n

• 周期

  如果对于一个整数 p，\forall 1 \le i \le n - p,s_i = s_{i+p}。p 是 s 的一个周期。这等价于 [1,n-p] 与 [1+p,n] 完全相同，即 s 有一个长度为 n-p 的 Border

  或者说，s 是由前缀 [1,p] 不断重复构成的

• 性质一：若 p,q 均为 s 周期，p+q \le n，\gcd(p,q) 也是 s 周期

  不妨设 p>q。考察 p-q 是否作为周期

  若 i > q，s_i = s_{i-q} = s_{i-q+p}

  若 i < p，s_i = s_{i+p} = s_{i+p-q}

  然后辗转相减即可

• 性质二：若 s' 为 s 前缀，s 有周期 a，s' 有周期 b。b \mid a，\mid s' \mid \ge a，则 s 有周期 b

• 性质三：若 t 出现于 s 的 [p_1,p_1+m),[p_2,p_2+m)。且这两个区间有交，则 t 有 \left \vert p_1 - p_2 \right \vert 的周期

• 性质四：如果 t 的长度不小于 s 的一半，其在 s 中匹配的起始位置构成等差数列

  只有匹配 \ge 3 次时有意义，取出第一二次匹配，和任意一次匹配起始位置 p_1,p_2,p_3，最后一次 p_4

  设 d = p_2 - p_1,q = p_3 - p_1。则 d,q 为 t 周期。设 p_{\min} 为 t 最小周期。显然有 p_{\min} \mid d,q，同时如果 p_{\min} \neq d，可以取得一个比 p_2 更靠前的匹配，故 d = p_{\min}

  因为 d \mid q，所有匹配的开始位置模 d 相等，同时 t 完全覆盖了 s[p_1,p_4+m)，故看出 s[p_1,p_4+m),t 均有周期 d

  现在其实只指出 [p_1,p_4] 中模 d 与 p_1 同余的起始位置都匹配了 t，而没有指出其他位置不行。但假设其他位置可以，会导致 t 拥有比 d 更小的周期，矛盾！

  （我没看出来指出 d = p_{\min} 有什么意义）

• 性质五：s 长度 \ge \dfrac{n}{2} 的 Border 长度构成等差数列

  记最长 Border 长度为 n-p，另一 Border 长度为 n-q，则 p,q \le \dfrac{n}{2}，所以 p+q \le n，\gcd(p,q) 也是 s 一个周期，n-\gcd(p,q) 也是 s 一个 Border

  而 n - \gcd(p,q) \le n-p，也就是说 \gcd(p,q) \ge p，即 p \mid q。公差为 p

  然后对于所有 p \mid q，q 都是 s 周期，所以 n-q 也是 Border

• 性质六：s 所有 Border 长度从大到小，可以划分为 O(\log n) 段等差数列

  久 等 了

  取出所有 \ge \dfrac{n}{2} 的 Border，记最短的长度为 T。我们希望说明：T \le \dfrac{3}{4}n

  考察最小周期 p，如果 p \le \dfrac{n}{4}，从最长的开始减，必然不会停在 n \ge \dfrac{3}{4}n 时。如果 p > \dfrac{n}{4}，最长的就 < \dfrac{3}{4}n

• 回文串与 Border

  对于一个回文串 s，其前缀 s' 也是回文串的充要条件是 s' 是 s 的 Border

  用 [1,m] 表示 s'，必要性：任取 1 \le i \le m，s_i = s_{m-i+1} = s_{n-i+1}

  充分性：任取 1 \le i \le m，s_i = s_{n-m+i} = s_{m-i+1}