Border Theory
持续更新中！！！更个屁，无线停更！
前言：
KMP 学傻了，看 skyh 说啥 border 树，跑来学 border 理论
洛谷云剪切板：https://www.luogu.com.cn/paste/gfkqhuyb（有小差别）
目录
基本定义
假设你们都知道串串是啥 .
其实正片文章都在混淆字符串 \(S\) 和字符串 \(S\) 的长度 \(|S|\)，意会一下 .
约定：
- \(S\) 的长度是 \(|S|\) .
- \(\Sigma\) 是字符集 .
- \(s[l:r]\) 是子串 \([l,r]\) .
- \(s[i]\) 是 \(s\) 的第 \(i\) 个字符，\(s_i\) 也是 .
- 字符串 \(A,B\) 拼接：\(AB\).
- \(S\) 长度为 \(k\) 的前缀、后缀：\(\operatorname{pre}(S,k)\)，\(\operatorname{suf}(S,k)\) .
- 然后如果一个 \(p\) 满足对一个串串 \(S\) 都有 \(s_i = s_{i+p}\)，则 \(p\) 是 \(S\) 的一个周期（period），若 \(p\mid n\) 则称为整周期 .
- \(p\) 的最小周期的长度记为 \(\operatorname{per}(u)\) .
若俩字符串 \(S, T\) 满足：
- \(S\neq T\) .
- \(S\) 即是 \(T\) 的前缀又是后缀 .
则称 \(S\) 是 \(T\) 的一个 border .
定义 \(\operatorname{border}(S)\) 表示 \(S\) 的所有 border 构成的集合 .
\(S\) 长度最长的 border 记作 \(\operatorname{maxbd}(S)\) .
后面叙述大概隐含一个 原串 \(S\)，所有 border 都是 \(S\) 的 border .
Period 与 Border
\(S[1:p]\) 是 \(S\) 的 border \(\Longleftrightarrow\) \(|S|-p\) 是 \(S\) 的周期，如图（或者看 这个） .
前缀函数 / KMP 自动机
因为 \(S\) 的所有 border 都是 \(S\) 的前缀，所以我们可以用一个下标表示出来 .
定义 \(\pi_i\) 表示 \(S[1:i]\) 的最长 border 长度 .
有可能你会发现 \(\pi\) 就是只有一个串串 \(S\) 的 AC 自动机的 fail 指针 .
然后显然有
定理 \(\mathbf 1\)
\[\operatorname{border}(S) = \operatorname{border}(\operatorname{maxbd}(S)) + \operatorname{maxbd}(S)
\]
这个非常显然吧 .
然后显然 border 的 border 还是 border，所以我们不断跳这个 \(\pi\) 就能求出全部 border 了 .
习题：Seek the Name, Seek the Fame .
KMP 算法
这块可以跳过去 .
KMP 大概就是 AC 自动机跳的过程
习题：
Border 树 / 失配树
对于每个 \(u\)，连边 \(u\leftrightarrow \pi_u\)，就成了 border 树（或者叫失配树）.
然后剩下的就看题吧 .
一个串串 \(S\)，多组询问，求两个前缀的最长公共 border .
border 树上每个点的祖先都是它的 border .
然后点的定义就是前缀 .
于是题目要求的这玩意就是 border 树上 LCA，没了 .
求给定字符串所有前缀的最大周期长度之和 .
周期和 border 对应，于是问题转换为求每个前缀的最小非空 border .
是不是就是 border 树上最浅祖先啊，暴跳就完了 .
求 \(S\) 的每个前缀 \(\leq\) 长度一半的 border 个数 .
当时学 KMP 的时候就是混过去的，现在终于知道咋做了，，，
建出 border 树，然后因为答案具有单调性，可以分两种做法：
- 倍增 .
- 大概是做一个限制长度的 KMP，然后复杂度可以均摊？？
关于周期的基本定理
定理 \(\mathbf 2\)（Weak Periodicity Lemma，WPL）
一个字符串 \(S\)，若其有 \(q\) 和长度为 \(q\) 的周期，且 \(p+q \leq |S|\)，则 \(s\) 有长度为 \(\gcd(p,q)\) 的周期 .
不失一般性，设 \(p>q\)，考虑证明 \(p-q\) 也是周期，就可以辗转相减搞出 \(\gcd\) 了 .
根据 period 的定义，\(\forall i\):
- 当 \(i<p\) 时，\(s_i=s_{i-q}=s_{i-q+p}=s_{i+(p-q)}\) .
- 当 \(i>q\) 时，\(s_i=s_{i+p}=s_{i+p-q}=s_{i+(p-q)}\) .
即 \(\forall i\)。\(s_i = s_{i+(p-q)}\)，从而 \(p-q\) 是周期 .
Q.E.D.
Bonus:
Periodicity Lemma
一个字符串 \(S\)，若其有 \(q\) 和长度为 \(q\) 的周期，且 \(p+q-\gcd(p,q) \leq |S|\)，则 \(s\) 有长度为 \(\gcd(p,q)\) 的周期 .
定理 \(\mathbf 3\)
对于串串 \(u,v\)，若 \(2|u|\geq|v|\) ，则 \(u\) 在 \(v\) 中的匹配位置必为等差序列 .
显然只需要考虑匹配至少 \(3\) 次的情况 .
考虑 \(u\) 在 \(v\) 中的第 \(1,2\) 次匹配 \(u_1,u_2\)，还有随便一个匹配 \(u_x\) .
设 \(u_1,u_2\) 间距为 \(d\)，\(u_2,u_x\) 间距为 \(x\)，如图 .
(因为 cnblogs 的 \(\TeX\) 不支持 \xleftrightarrow 于是换成图片了）
不难发现 \(d,q\) 都是 \(u\) 的周期，于是根据 WPL，\(r = \gcd(d,q)\) 亦然 .
设 \(u\) 的最小周期为 \(p\le r\)，显然 \(p\mid r\mid d\)，可以考虑反证法 WPL .
然而 \(d\) 显然是 \(u_1\cup u_2\) 的周期，于是 \(p\) 也是 \(u_1\cup u_2\) 的周期吧 .
若 \(p<d\)，将 \(u_1\) 右移 \(p\) 又形成一次匹配，矛盾！
于是显然可以推出 \(p=d\) .
又 \(d = p\le r = \gcd(d,q)\)，从而 \(d\mid q\) .
看看 \(d\mid q\) 意味着啥？是不是就证完了 .
Q.E.D.
推论（？）：
对于串串 \(u,v\)，若 \(2|u|\geq|v|\) ，则 \(u\) 在 \(v\) 中的匹配位置形成等差序列 .
若它的项数不小于 \(3\)，则其公差等于 \(u\) 的最小周期 .
Border 的结构
定理 \(\mathbf 4\)
\(S\) 的长度不小于 \(|S|/2\) 的 border 长度构成一个等差序列 .
设长度最大的 border 为 \(n-p\) ，另一个 border 长度为 \(n-q\)（即 \(p,q\) 是周期，且均有 \(p,q\leq n/2\) .
由 WPL 得 \(\gcd(p,q)\) 也是 \(S\) 的周期，所以存在长度为 \(n-\gcd(p,q)\) 的 border .
根据 \(n-p\) 为最长 border 的假设，要满足 \(\gcd(p,q)\geq p\) 即 \(p\mid q\) .
这个整除意味着等差序列，和上面那个 定理 \(\mathbf3\) 类似 .
长度小的 border？
定理 \(\mathbf 5\)
\(S\) 的所有 border 长度构成 \(O(\log |S|)\) 个等差序列 .
首先，将该串的长度达到 \(n/2\) 的 border 划分成一个等差序列 .
然后取出长度最小的 border \(T\) .
然后可以证明 \(|T|\le \dfrac 34|S|\)，如下 .
- 若最小循环节 \(d\leq |S|/4\)，不断从最长 border 减去 \(d\) 则必然有 \(|T|\le \dfrac 34|S|\) .
- 若最小循环节 \(d>|S|/4\)，则直接证完 .
然后根据我们平凡的 定理 \(\mathbf 1\)，其他 border 都是这个 \(T\) 的 border，于是每次缩小 \(3/4\)，就是 \(\log\) 级别的了 .
Q.E.D.
Bonus：更紧的界：\(\lceil\log|S|\rceil\) .
Prefix-Suffix (PS)
将 \(s\) 的所有 border 按长度分类：
\[x\in[1,2),[2,4),[4,8),\cdots,,[2^{k-1},2^k),[2^k,n)
\]
若 \(|u|=|v|\)，记 \(\operatorname{PS}(u,v)=\{k:\operatorname{pre}(u,k) = \operatorname{suf}(v,k)\}\) .
是不是很像 border！！
然后令 \(\operatorname{LargePS}(u,v) = \{k\in\operatorname{PS}(u,v):k\ge |u|/2\}\) .
则 \(S\) 在 \([2^{i-1},2^i)\) 内的 border 长度集合就是 \(\operatorname{LargePS}(\operatorname{pre}(S,2^i),\operatorname{suf}(S,2^i))\) .
定理 \(\mathbf 6\)
\(\operatorname{LargePS}(u,v)\) 构成一个等差数列 .
都是 \(\operatorname{pre}(u,\max\{\operatorname{LargePS}(u,v)\})\) 的 border，可以看金策大爷的图 .
然后我们发现 定理 \(\mathbf 5\) 其实是这玩意的推论 .
子串周期查询
一个长度为 \(n\) 的字符串 \(S\)，每次询问一个子串 \(t\) 的所有周期 .
用 \(O(\log)\) 个等差序列表示 .
所有周期等价于询问所有 border .
按 border 长度 \(x\) 分类：
- Case 1. \(x\in[2^{i-1},2^i]\) .
- Case 2. \(x\in[2^k,r-l+1]\) .
根据前面说的啥 \(\operatorname{PS}\)，我们可以知道 Case 1 就是要求 \(\operatorname{LargePS}(\operatorname{pre}(t,2^i),\operatorname{suf}(t,2^i))\) .
若 \(u\) 是一个 Large Prefix-Suffix (LargePS)，则 \(\operatorname{pre}(t,2^i)\) 是 \(u\) 的前缀，\(\operatorname{suf}(t,2^i)\) 是 \(u\) 的后缀 .
求出 \(\operatorname{pre}(t,2^{i-1})\) 在 \(\operatorname{suf}(t,2^i)\) 中匹配的所有位置，还有 \(\operatorname{suf}(t,2^{i-1})\) 在 \(\operatorname{pre}(t,2^i)\) 中匹配的所有位置，移位取交集即可 .
Case 2: 因为 \(L=2^k\ge m/2\)，所以我们的任务 — 求出 \(t\) 的所有长度不小于 \(L\) 的 border，是不是就是求 \(\operatorname{PS}_{\ge L}(t,t)\) 啊，和 Case 1 做法相同 .
然后我们看看具体怎么做：
Task 1. 怎么求出匹配的所有位置？？？
Internal Pattern Matching (Easy ver.)
一个字符串 \(u\)，多次询问，每次给出其两个子串 \(v,w\)（满足 \(2|v|\ge |w|\)），询问 \(u\) 在 \(v\) 中的所有匹配位置 .
特殊性质：\(v\) 是 \(2\) 的幂 .
也就是要实现一个 \(\operatorname{succ}(v,i)\)，能求出 \(v\) 在 原串 \(s\) 中起点不小于 \(i\) 的第一次匹配（以及反过来的 \(\operatorname{prev}(v,i)\)）.
因此只需要把 \(s\) 中所有长度为 \(2\) 的次幂的子串拉出来排序，相同的子串按起始位置排序即可 .
这个过程类似于倍增求 SA .
然后查 \(\operatorname{succ}\) 的时候二分就完了 .
Task 2. 等差序列取交集？？？
可以证明俩等差序列公差相等，具体比较牛逼，看金策大爷的课件吧 .
于是我们目前做到的是：
- 空间 \(O(n\log n)\) .
- 预处理 \(O(n\log n)\)，询问 \(O(n\log^2 n)\) .
- 在线
的算法 .
一个小优化：
注意到 \(\operatorname{succ}\) 询问时只关系起点在 \([i,i+|v|]\) 的匹配 .
于是将 \(s\) 按 \(|v|\) 的间隔分段，每段是一个等差数列 .
所有非空段的东西丢进 Hash Table，就可以单次一个 \(\log\) 了 .
预处理期望 \(O(n\log n)\) .
子串周期查询可以在 BJWC Border 的四种求法 测（题目要求区间最大 Border 长度）.
Internal Pattern Matching (IPM)
一个字符串 \(S\)，多次询问，每次给出其两个子串 \(u,v\)（满足 \(2|u|\ge |v|\)），询问 \(u\) 在 \(v\) 中的所有匹配位置 .
我们是不是解决了 \(u\) 是二的幂的情形，而且还做到了 \(O(1)\) 询问？
如果不是你就等差数列移位求交集，复杂度变成询问 \(O(\log n)\) .
等差数列移位求交集的过程是不是类似 ST 表啊
子串循环同构判定
一个字符串 \(S\)，多次询问，每次给出其两个长度相等的子串 \(u,v\)，询问 \(u\)，\(v\) 是否循环同构 .
如果是就输出所有移位长度（表示成等差序列） .
我会最小表示法！
几个平凡的结论：
- 一个串串 \(s\) 的最小周期是 \(p\)，如果 \(p\mid n\)，则 \(s\) 只有 \(p\) 个本质不同的循环移位，每种出现 \(n/p\) 次 .
- \(s,t\) 循环同构 \(\Longleftrightarrow\) \(s\) 是 \(tt\) 的子串 .
根据第二个是不是 IPM 判定就好了？
然后我们看看怎么求所有移位长度 .
设 \(u=ab\)，\(v=ba\)，不失一般性，令 \(|a|\ge|u|/2\) .
记 \(w=\operatorname{pre}(a,\lceil|u|/2\rceil)\)，IPM 查询 \(w\) 在 \(v\) 中出现的所有位置 \(j_{1\dots m}\)（是一个公差为 \(q\) 的等差序列）
根据 定理 \(\mathbf 3\) 的推论，当 \(m\ge 3\) 时，\(q=\operatorname{per}(w)\) .
设
- \(u\) 最长的拥有周期 \(q\) 的前缀长度为 \(d_u\) .
- \(v[j_1:|v|]\cdot v\) 最长的拥有周期 \(q\) 的前缀长度为 \(d_v\) .
于是 \(j_t\) 是合法起始点的必要条件就是 \(\min\{|u|,d_v-(i-1)q\} = d_u\) .
然后就可以轻易 \(O(1)\) 求移位长度了 .
手机扫一扫
移动阅读更方便
你可能感兴趣的文章