Broder 和 Period 的性质

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135121825

一个字符串的 border 可以被划分 $O(\log n)$ 段等差数列

• border 和 Period 一一对应

现在等价于求 Period 为等差序列。

设有 $p_1,p_2$ 的Period。

1. $p_1,p_2\ge \frac {|S|} 2$ ，则由 $\gcd(p_1,p_2)\le \frac {|S|} 2$

2. $p_1+p_2\ge |S|$ ，则首项和公差都大于

Period长度自然减半

倍增 $\log n$ 次，所以可以划分成 $\log n$ 个等差数列。

---

同理，我们可以在fail树上进行。