Part 1 Border，Period 理论
设有一长 n 的字符串 S。
1.1 定义
-
Border：
满足 1≤k<n 且 S[1,k]=S[n−k+1,n] 的 k。
不妨把 S 的 Border 放入集合 B(S) 中。
记 Bl(S) 为 max{k∣k∈B(S)}。
-
Period（周期元）：
满足 1≤k<n 且 ∀1≤i≤n−k 都有 Si=Si+k 的 k。
不妨把 S 的 Period 放入集合 P(S) 中。
1.2 基本性质&定理
1.2.1 对偶性
k∈B(S)⇔n−k∈P(S)
证明考虑把已知的等价关系画出来。
1.2.2 弱周期定理
x,y∈P(S),x+y≤n⇒gcd(x,y)∈P(S)
证明
不妨令 x<y。
仅需证明 y−x∈P(S)，辗转相除会出手。
对于 Si：
- i≤x：i+y≤n，Si=Si+y=Si+y−x；
- i>x：Si=Si−x=Si+y−x；
1.2.3 Border 的传递性
y∈B(S[1,k]∣k∈B(S))⇒y∈B(S)
即 Border 的 Border 还是 Border。
证明考虑画画。
1.2.4 Border 的区间包含单调性
Bl(S[l+1,r−1])≥Bl(S[l,r])+2
1.3 Border 的结构
1.3.1 Border 的树状结构
B(S)=B(S[1,Bl(S)])+{Bl(S)}
证明
根据传递性，有 B(S[1,Bl(S)])⊂B(S)。
由于 Bl(S) 是 S 最长的 Border，所以 B(S)−B(S[1,Bl(S)])={Bl(S)}。
这启发我们可以建出 n 个点的树，每个点代表 S 的一个前缀，i 的父亲为 Bl(S[1,i])。
容易发现这棵树的根为 1，每个节点的 B 集合就是它到根路径上的节点集合。
实际上这就是 AC 自动机的 fail 树。
1.3.2 Border 的等差数列结构
1.3.2.1 引理
所有满足 2k≥n 的 Border k 构成一个等差数列
证明
考虑 P(S) 中 ≤⌊2n⌋ 的元素 x 构成的集合 Ps(S)，根据弱周期定理，显然 r=min{Ps(S)} 是 Ps(S) 中所有元素的因子。
且由于 r 是最小的 Period，Ps(S) 一定为 {kr∣1≤k,kr≤⌊2n⌋} 即 r 的正整数倍构成的集合。
根据对偶定理，A={n−kr∣1≤k,kr≤⌊2n⌋}⊆B(S)，并且 A 包含所有 2k≥n 的 Border k。
也就是说，满足 2k≥n 的 Border k 构成了一个首项为 n−r，公差为 −r 的等差数列。
1.3.2.2 定理 - 等差数列结构
B(S) 构成 O(logn) 个等差数列
证明
根据引理 1.3.2.1，所有满足 2k≥n 的 Border k 构成了一个等差数列。
设 l=max{k∣k∈B(S),2k<n}，类比 1.3.1（树状结构）的证明，易知去除该等差数列后剩下的 Border 集合为 B(S[1,l])+{l}。
那么在 S[1,l] 上调用一次引理 1.3.2.1，可以实现继续砍半。
由于每次砍半，所以总共会得到 O(logn) 个等差数列。
等差数列的寻找方法
这里给出一种寻找等差数列的方法：（该方法把 n 也当作 S 的 Border）
- 找到 S 的极长 Border k，设 l=n−(n−k)⌈n−kn−⌊2n⌋⌉；
- 加入新的首项为 n−(n−k)⌈n−kn−⌊2n⌋⌉，末项为 n，公差为 n−k 的等差数列；
- 找到 S[1,l] 的最长 Border p，递归处理 S[1,p]；
1.4 例题
