说起border理论，大家第一次接触这个东西，可能是在 最小回文划分 或者 论战捆竹竿，或者压根就是这篇blog。这个看起来非常复杂，但是实际上并没有那么可怕哦。
参考 command_block Border理论小记，以及ix35 NOI 一轮复习 II：字符串。
定义，简单结论和约定
周期就是周期。
\(s\)的一个border是一个串，它既是\(s\)的前缀又是后缀。这个容易用kmp求出，实际上kmp干的就是这个事情。我们直接用长度表示border，也就是说一个border \(b\)中的\(b\)既是长度又是字符串，根据语境应该容易判断它的具体含义。
周期和border是一一对应的。如果一个周期长为\(k\)，那么就有一个border长为\(n-k\)。
两个重要结论和几个不重要结论
重要结论1(弱周期引理) 如果\(s\)有两个周期\(a,b\)，并且\(a+b\leq n\)，那么\(\gcd(a,b)\)也是\(s\)的周期。
证明 不妨设\(a>b\)，那么证明\(a-b\)也是周期，然后作辗转相减 :
-
对于\(i\geq b\)，有\(s_i=s_{i-b}=s_{i+a-b}\)
-
对于\(i\leq n-a\)，有\(s_i=s_{i+a}=s_{i+a-b}\)
，而\(b\leq n-a\)，所以就证完了。
周期引理 把\(a+b\leq n\)换成\(a+b-\gcd(a,b)\leq n\)。
证明 不会，可以看一看ix35的blog。
引理1 \(s\)中任意两个border \(a,b\)，如果\(a<b\)，那么\(a\)也是\(b\)的border。这是border的子结构性质。
证明 废话。
引理2 \(s\)中长度不超过一半的周期都是其中最短的周期的倍数，并且构成等差数列。对应地，长度至少是一半的border构成等差数列。
证明 根据弱周期引理，考虑所有这样的周期的\(\gcd\)，它一定是最小的，所以长度不超过一半的周期一定是它的所有倍数，而一个数的所有倍数实在是等差数列。
重要结论2 \(s\)的所有border形成\(O(\log n)\)个值域不交的等差数列，周期是对应的。
证明 考虑最长的border，设为\(b_0\)，那么根据引理1，别的border都是它的border，于是根据引理2，长度至少是\(\frac{b_0}{2}\)的border构成等差数列。
考虑除此之外最长的border，你发现这个可以递归下去，\(\log\)次就会变成\(0\)，所以一共构成最多\(\lceil\lg n\rceil=O(\log n)\)个值域不交的等差数列。
要找到这些等差数列，直接做就好了。
实际上我们在说一道题是弱周期引理的时候，很多时候其实是说它用到了重要结论2。
几个例题
子串周期查询，以及内部模式匹配
给一个串，每次给一个区间，查询这个区间的周期构成的等差数列们。\(n\leq 10^5\)。
这是一个复杂的问题。
鏼和19年集训队论文都给出了1\(\log\)做法，所以这确实是经典题（?
我们先转化成border。
基本子串字典 Dictionary of Basic Factors, DBF
定义基本子串是长为\(2^k\)的子串。
考虑sa的倍增算法，你发现它处理过程中的信息量其实很大，我们把这些全都存下来，就相当于把每个长度的基本子串分别排了个序。
这个结构可以用于快速比较两个子串，具体做法类似于st表，当然sa也可以做这个事情。
它的优势在于，在禁止hash的前提下可以容易地扩展到树上，也就是比较两条祖先-后代链。在树上，sa的height算不动了，这导致除了hash我们想不到可以用什么来判断相等的情况了，而dbf就不会出现这样的问题。使用长剖可以做到\(O(1)\)，当然这也只有理论价值，因为你不会为了避免hash而去学习dbf。
当然这里选择它是因为基本子串和border的等差数列性质结合的很好。
简单做法
假设现在问的区间是\(s\)。
考虑\([2^k,2^{k+1})\)的所有border，它们必然构成一个等差数列。我们对每个这样的区间跑一遍即可。当然对于最后一个区间\([2^k,\vert s\vert]\)需要一些特殊处理，不过方法是完全一样的。
要找到这样的border，考虑它们就是 同时是\(\mathrm{pre}(s,2^{k+1})\)的前缀和\(\mathrm{suf}(s,2^{k+1})\)的后缀，并且长度至少是\(2^k\)的串。
随机想一想，你发现这个串一定包含\(\mathrm{pre}(s,2^k)\)作为前缀，并且包含\(\mathrm{suf}(s,2^k)\)作为后缀。
考虑求出\(\mathrm{pre}(s,2^k)\)在\(\mathrm{suf}(s,2^{k+1})\)中的所有匹配位置，以及\(\mathrm{suf}(s,2^k)\)在\(\mathrm{pre}(s,2^{k+1})\)中的所有匹配位置，然后加加减减一下，求个交就好了。
为什么这么做?我们有一个重要引理说明这样求交的优秀性质。
引理3 如果\(s\)的长度至少是\(t\)的一半，那么\(s\)在\(t\)中的匹配位置构成一个等差数列，并且如果匹配至少三次，这个等差数列的公差是\(s\)的最小周期。
证明 匹配不到三次的情况显然。
考虑因为\(s\)的长度至少是\(t\)的一半并且匹配了至少三次，那么相邻两次匹配之间一定有交。考虑前两次匹配的并\(a\)，\(s\)当然是\(a\)的一个border，故\(\vert a\vert-\vert s\vert\)也就是两次匹配的距离是\(a\)的一个周期，当然也是\(s\)的周期。
考虑前两次匹配，假设它们的位置分别是\(i,j,k\)。如果\(j-i\)不是最小周期，那么在这两次匹配之间必然还有一次匹配，这样第二次匹配就不是真正的第二次匹配了，所以\(j-i\)一定是\(s\)的最小周期。
再考虑最后一次匹配，它和第二次匹配一定有交，所以这中间的匹配确实构成了一个等差数列。
现在我们来看看引理3有什么用。它说明了，刚才我们要求的匹配位置分别构成等差数列。
等差数列求交是容易的，只需要exgcd一发就行了。怎么求出这两个等差数列?
刚才的证明也给出了一个想法 : 我们只需要求出第一次，第二次和最后一次匹配位置，就可以得到这个等差数列。容易发现问题可以转化为怎么求一个串\(u\)在一个区间内的第一次出现，第二次和最后一次是等价的。
考虑利用dbf。我们只需要找到\(u\)的所有出现位置，这是可以用dbf求出的，然后就可以在上面二分搞定了。
具体地，dbf给所有某一长度的基本子串排了序，那么相同的一定挨在一起，这样就可以求出每个基本子串的所有出现位置，从而可以二分找一个基本子串在某个区间的第一次出现。
两个优化
注意到距离1\(\log\)还有两个瓶颈 : exgcd的等差数列求交，以及找一个基本子串在某个区间中的前两次和最后一次出现。
对于第一部分，我们给出引理4。
引理4 有四个串满足\(\vert x_1\vert=\vert y_1\vert\geq\vert x_2\vert=\vert y_2\vert\)，并且\(x_1\)在\(y_2y_1\)中出现至少三次，\(y_1\)在\(x_2x_1\)中出现至少三次，那么\(x_1,y_1\)的最小周期相等。
证明 反证。设\(x_1,y_1\)的最小周期分别是\(x,y\)，不妨假设\(x\)更大。
考虑\(x_1\)在\(y_2y_1\)中的最后一次匹配，设这次匹配中\(x_1\)和\(y_1\)的交为\(z\)。
引理3说明\(x_1\)的匹配们构成等差数列，并且公差是\(x\)。因为这是最后一次匹配，前面至少匹配了两次，并且\(\vert x_1\vert\geq\vert y_2\vert\)，所以我们知道有\(\vert z\vert\geq 2x\geq x+y\)。根据弱周期引理，我们知道\(z\)有周期\(\gcd(x,y)<x\)。但是\(\vert z\vert\geq 2x\)，这说明\(\gcd(x,y)\)也是\(x_1\)的周期，所以\(x\)并不是\(x_1\)的最小周期。
这个引理给出了一个非常强的条件 : 如果我们上面要求交的两个等差数列长度都至少是\(3\)，它们的公差一定相同，否则我们可以枚举小的那边看它是不是在大的里面，容易做到\(O(1)\)。
对于第二部分，注意到我们每次查询的时候，查询区间长度都是\(\vert u\vert\)，这启示我们做一个分块。
求出每个基本子串在原串中的所有匹配位置之后，我们把原串按照\(\vert u\vert\)长度分块，那么每个查询都只会包含一个块前缀和一个块后缀，我们只需要维护每个块每个前/后缀的最小/次小/最大值。注意到直接这么做需要\(O(n^2\log n)\)空间，但是实际上有效信息只有\(O(n\log n)\)，我们可以用hash table来维护。
这样就\(O(n\log n)-O(1)\)了，不过是期望的，你可以用phf那一套去掉查询的期望（
实际上刚才我们用dbf所做的事情称为内部模式匹配 Internal Pattern Matching, IPM。刚才那是弱化版，因为只问基本子串，此时我们可以做到\(O(n\log n)-O(1)\)。
如果把询问串换成任意\(u,v\)，只要求满足\(2\vert u\vert\geq\vert v\vert\)，应该怎么做呢?
考虑分别求\(\mathrm{pre}(u,L),\mathrm{suf}(u,L)\)的匹配位置然后取交，其中\(L\)是\(\leq\vert u\vert\)的最大\(2^k\)。注意到不一定有\(2L\geq\vert v\vert\)，所以我们有可能需要把\(v\)分成两份来处理，这个的合并是简单的，于是下面我们假设有\(2L\geq\vert v\vert\)。
要求这个东西是简单的，用刚才弱化版的做法就可以做到\(O(n\log n)-O(1)\)。问题在于怎么求交。
做法比较诡异。找一个长为\(L\)的位于\(\vert u\vert\)中间的子串，容易知道它和\(\mathrm{pre}(u,L),\mathrm{suf}(u,L)\)的交长度至少是\(\frac{L}{2}\)。显然我们可以对这三个串都跑一遍然后取交，中间那个串的目的是作一个必要限制来获得性质更优秀的答案范围。
如果三个串都在\(v\)中匹配至少五次，那么就可以说明它们的最小周期都小于\(\frac{L}{4}\)(因为第一次和最后一次匹配的位置差在\(L\)以内)，因为交的长度至少是\(\frac{L}{2}\)，它们的最小周期都相等，这里的证明留作练习，答案在下一节。我这个好像比鏼要松/yun
存在某种方式对dbf进行优化做到\(O(n)-O(1)\)，不过我并不会。并没有兴趣阅读串串方面的论文。
这是练习的证明。
引理temp1 \(s\)的两个长\(L\)的子串，它们的交\(\geq\frac{L}{2}\)，并且最小周期都\(\leq\frac{L}{4}\)，则它们的最小周期相等。
证明 反证，考虑设两个子串的最小周期分别是\(a<b\)，考虑中间相交的那一段，根据弱周期引理有\(\gcd(a,b)\)也是中间那一段的周期，故\(\gcd(a,b)\leq a<b\)也是两个串的周期，所以第二个串的最小周期并不是\(b\)。
如果你做出来这个，你可能已经具有基本的串串推导能力了（
WC2016 论战捆竹竿
给一个串\(s\)，有一个串一开始是\(s\)，你可以进行任意次操作，每次可以把\(s\)去掉一个border前缀接上去，问可以接出\(w\)以内的多少长度。\(n\leq 5\times 10^5,w\leq 10^{18}\)，多组数据。
抽象出来是，\(s\)的周期的线性组合可以表示\(w-n\)以内的多少数。
这个串一看就是弱周期引理，而数数的部分一看就是同余最短路嘛。
考虑直接取最长的周期作为同余最短路的膜数，那么应该如何对一个等差数列优化建图?
不过优化建图是复杂的，一方面对等差数列优化建图看起来复杂度极高，另一方面优化了还需要Dij多\(\log\)。
不过同余最短路性质很好，我们可以分开考虑每个等差数列的贡献，容易发现这样做还是可以保证正确性，因为仍然可以得到所有可能的方案。
任意膜数看起来还是比较复杂。那么我们可以考虑简化一下，对于等差数列\(ai+b\)，我们在\(\bmod{b}\)意义下跑同余最短路，这样好像简单多了。
根据经典结论，转移会形成\(\gcd(a,b)\)个环，环之间是独立的。
问题是怎么破环成链，你发现全是正权所以每个环的\(\min\)一定不会被更新。于是我们可以对于每个环，从环上的\(\min\)出发，维护一个单调队列，转一圈进行转移。
现在我们的主要问题就是怎么改变同余最短路的膜数。这个事情听起来非常复杂……
不过你发现，实际上同余最短路的每个位置也是描述了一个等差数列，我们只要处理掉第一项的转移，接下来问题又变回了加一个等差数列来转移，可以直接按照上面的方式计算，并且这里没有项数的限制，所以可以省去单调队列。
第一项的转移也简简单单，我们要把\(\bmod{b}\)变成\(\bmod{b^\prime}\)，只需要把\(dis(i)\)贡献到\(dis(dis(i)\bmod{b^\prime})\)即可。
HNOI2019 JOJO
人话题意说的是，维护一个串，支持push_back一串相同字符，可持久化，每次操作之后查询每个前缀的最长真border长度之和。
当然是kmp。
首先考虑怎么搞定那个 一口气加入1e4个字符，一个直接的想法是直接把每次操作看成一个二元组，然后直接在这上面进行kmp。
先考虑如何一口气转移一段。考虑这时候会不能考虑什么样的情况。你发现这个border作为前缀出现的时候，最后一段可能不完全匹配；作为后缀出现时，第一段可能不完全匹配。
如果只看二元组序列，我们可以这样判定是否能匹配上 : 后缀的第一段长度至少是前缀的第一段长度，后缀的最后一段长度不超过前缀的最后一段长度。
同时如果你学过kmp，你知道kmp就是 匹配不上就跳fail，所以我们仍然可以按照这个来跑kmp。
考虑如何计算段中间字符的贡献，考虑这一段最后一个字符匹配的位置，我们只需要考虑这个位置往前还有多少个相同字符。举个例子 :
-
考虑
...abbbb和...abb的匹配，右边最后一个b匹配到了左边的第二个b，这样右边第一个b就匹配到了左边第一个b -
注意
...abb和...abbbb是不可能匹配的，这说明这一段的fail一定是一个等差数列，可以直接求和
。
最后一个问题是，考虑我们怎么才能把kmp可持久化掉，你发现最简单的方法就是考虑acam(指trie图)的加点是严格的，我们可以把kmp也建成一个类似trie图的东西，不妨称为kmp图。
但是这里字符集巨大(2.6e5)，不过kmp图的转移大部分是继承，只有\(O(1)\)的修改，所以我们可以直接可持久化线段树搞定。
另一个把kmp变成严格的方法是使用弱周期引理。考虑我们在kmp失配的时候会跳border，然后你发现对于每个等差数列，实际上只有最长的那个border是有用的，因为短的那些都是它砍去了一个周期得到的，所以如果最长的那个会失配，那些短的也会失配。
可以用一个可持久化数组维护所有border构成的等差数列们，复杂度是两个\(\log\)，可以离线变成可撤销化数组变成一个\(\log\)。
事实上我感觉和弱周期引理结合最好的字符串数据结构就是kmp和pam。