废话
波论好难，学不懂。
一点一点推罢。
Border 的定义
一个字符串的最长真公共前后缀就叫 Border（这个「真」就表示其不和原字符串相同）。
刨开 Border，剩下的一部分被称作 Period。
\[\underbrace{\fcolorbox{000000}{66ccff}{\kern{70pt}}}_{\texttt{Border}}\overbrace{\fcolorbox{000000}{ffffff}{\kern{20pt}}\underbrace{\fcolorbox{000000}{66ccff}{\kern{70pt}}}_{\text{和前面的蓝色部分相同}}}^{\texttt{Period}} \]Border 是可以有重叠部分的：
\[\underbrace{\fcolorbox{000000}{66ccff}{\kern{70pt}}\overbrace{\fcolorbox{000000}{33667f}{\kern{30pt}}}^{\text{重叠部分}}}_{\texttt{Border}}\underbrace{\fcolorbox{000000}{66ccff}{\kern{70pt}}}_{\texttt{Period}} \]为什么剩下的部分要叫 Period？因为它是这个字符串的循环节，Border 没有重叠部分的情况是很显然的。
利用相等关系的传递性，下面三个青色部分是相同的。
\[\fcolorbox{000000}{33667f}{\kern{15pt}}\underbrace{\fcolorbox{000000}{66ccff}{\kern{40pt}}\fcolorbox{000000}{33667f}{\kern{15pt}}}_{\texttt{Period}}\underbrace{\fcolorbox{000000}{66ccff}{\kern{40pt}}\fcolorbox{000000}{33667f}{\kern{15pt}}}_{\texttt{Period}} \]所以 Period 是这个串的循环节。 如果还有重叠部分可以一直递归下去。
Border 的性质
令 \(\operatorname{Border}(S)\) 表示字符串 \(S\) 的所有 Border 组成的集合，令 \(\operatorname{maxBorder}(S)\) 表示字符串 \(S\) 长度最大的 Border。
那么有：
\[\operatorname{Border}(S) = \operatorname{Border}(\operatorname{maxBorder}(S)) \cup \left\{\operatorname{maxBorder}(S)\right\} \]就是一个字符串所有的 Border 是由它最大的 Border 和这个 Border 的所有 Border 组成的。
\[\underbrace{\overbrace{\fcolorbox{000000}{33667f}{\kern{45pt}}}^{\texttt{Border}\text{的}\texttt{Border}}\fcolorbox{000000}{66ccff}{\kern{15pt}}\fcolorbox{000000}{33667f}{\kern{45pt}}}_{\texttt{Border}}\fcolorbox{000000}{ffffff}{\kern{15pt}}\fcolorbox{000000}{33667f}{\kern{45pt}}\fcolorbox{000000}{66ccff}{\kern{15pt}}\overbrace{\fcolorbox{000000}{33667f}{\kern{45pt}}}^{\text{与青色部分相同}} \]（有重叠的情况懒得画了。）
Border 的前半部分的两段 Border 相同，而 Border 本身的两段也相同，从而前半段的 Border 和后半段的 Border 相同，所以是原字符串的 Border。
由此可见，Border 的 Border 可以利用相等关系的传递性，来证明是原字符串的另一个 Border。
而且并不存在一个 Border，使得它不是 \(\operatorname{maxBorder}(S)\) 且不属于 \(\operatorname{Border}(S)\)。
若存在，则它必定比 \(\operatorname{maxBorder}(S)\) 短，而它又是原串的 Border，所以它分别和 \(\operatorname{maxBorder}(S)\) 的左右两段相同，所以它又是 \(\operatorname{maxBorder}(S)\) 的 Border，矛盾。
如何求每个前缀的 maxBorder
详见 「BJWC2018 Border 的四种求法」一题。
朴素的求法是 \(\mathcal{O}(n^{2})\) 的。
注意到小标题「前缀」这一限定，令 \(nxt_{i}\) 表示 \(\operatorname{maxBorder}(S[1 .. i])\) 的长度（也对应着靠前的 Border 的结束位置）。若我们已知 \(nxt_{1 \sim i - 1}\)，那么可以快速求出 \(nxt_{i}\)。
KMP 包含了这一部分，这里不细讲，贴一个远古博客的链接。
而这个 \(nxt_{i}\) 常常会被称为 \(fail\) 指针，因为在字符串匹配失败时就是利用它快速跳转的。
若把每一对 \((fail_{i}, i)\) 看作一条树上的边，那么所有的边就组成了一棵失配树，总共有 \(n + 1\) 个点和 \(n\) 条边，有时候将题目放到失配树上来做会直观许多。
一个点到根的路径就包含了它所有的 Border。
每一个前缀在 \(S\) 中的出现次数就是其子树大小。
应该还有很多性质，但是还不了解。
习题
做一题写一题，咕咕咕。
标签：000000,operatorname,kern,fcolorbox,Border,maxBorder From： https://www.cnblogs.com/A-box-of-yogurt/p/18032741