看的是金策的字符串 ppt。
约定
- 字符串以 $1$ 为起始下标。
- $S[l,r]$ 表示字符串 $S$ 下标从 $l$ 到 $r$ 的子串。
- $\vert S\vert$ 表示 $S$ 的大小。
- $\operatorname{Border}(S)$ 表示字符串 $S$ 的 Border 组成的集合。
- $\operatorname{maxBorder}(S)$ 表示字符串 $S$ 的最大的 Border。
- 若无特殊提及，默认 $n$ 为字符串长。
相关定义
- Border：若 $T$ 为 $S$ 的 Border，则 $T$ 既是 $S$ 的真前缀，也是 $S$ 的真后缀。
- 周期：若 $p\in[1,\vert S\vert]$ 满足 $\forall i>p$，都有 $S_i=S_{i-p}$，那么 $p$ 是 $S$ 的一个周期。最小的 $p$ 是 $S$ 的最小正周期。当 $p\mid \vert S\vert$ 时，称 $p$ 为 $S$ 的一个整周期。
Border 与周期的定义实则上等价，故有如下关系：若 $T\in\operatorname{Border}(S)$，则 $p=\vert S\vert -\vert T\vert$ 是 $S$ 的一个周期。
性质
性质 1：$\operatorname{Border}(S)=\operatorname{maxBorder}(S)+\operatorname{Border}(\operatorname{maxBorder}(S))$。
这个就是 KMP 的理论基础，其实可以直接感性理解的。
性质 2 (Weak Periodicity Lemma)：$p,q$ 为 $S$ 的周期，若 $p+q\le\vert S\vert$，则 $\gcd(p,q)$ 也是 $S$ 的一个周期。
设 $d=p-q\quad(p>q)$。若 $i>p$，有 $S_{i-p}=S_{i-p+q}=S_{i-d}$。当 $i<p$ 时，有 $S_{i-q}=S_{i-q+p}=S_{i+d}$。
进一步的，有更强的周期引理（Periodicity Lemma）：$p,q$ 为 $S$ 的周期，若 $p+q-\gcd(p,q)\le\vert S\vert$，则 $\gcd(p,q)$ 也是 $S$ 的一个周期。
性质 3：若 $u,v$ 满足 $2\vert u\vert\ge \vert v\vert$，那么 $u$ 在 $v$ 中匹配位置呈等差数列。
当只有两个匹配时，显然成立。设第一次匹配与第二次匹配位置差为 $d$，第二次与第 $x$ 次匹配位置差为 $q$，如上图，显然都是 $u$ 的周期。
由 $2\vert u\vert\ge \vert v\vert$，有 $d+q\le \vert S\vert$，因而 $r=\gcd(d,q)$ 仍为 $u$ 的周期。设 $u$ 的最小周期为 $p\le r$。第二次匹配应该为 $u_1$ 向右移 $p$ 个单位的位置，而 $p\le d$，故 $d=p\le\gcd(d,q)$，因而 $d\mid q$。
另外，根据上述推导，$u$ 的最小正周期必然有 $p\le\dfrac{\vert u\vert}2$。
性质 4：对于 $T\in \operatorname{Border}(S)$ 满足 $\vert T\vert \ge \dfrac{\vert S\vert}2$ 的所有 $\vert T\vert$ 构成等差数列。
设 $\vert\operatorname{maxBorder}(S)\vert=\vert S\vert-p$，另一 Border 的长度为 $\vert S\vert-q$。则存在周期 $p,q$，和性质 3 类似，$\gcd(p,q)$ 也是 $S$ 的周期。因此 $n-\gcd(p,q)$ 也是 $S$ 的某个 Border 的长，$\gcd(p,q)\ge p\implies p\mid q$。
进一步，对于长度更小的 Border，考虑分类。
将 Border 长度划分成：
$$[1,2),[2,4),\cdots,[2^{k-1},2^k),[2^k,n)$$
对 $[2^k,n)$ 的情况已经讨论，下面考虑 $[2^{i-1},2^{i})$ 的情况。
对于 $\vert u\vert=\vert v\vert = n$，设 $F(u,v)=\{k\mid u[1,k]=v[n-k+1,n]\}$，$G(u,v)=\{ k\mid k\in F(u,v)\land k\ge \frac n2 \}$。
取 $u_i=S[1,2^i],v_i=S[n-2^i+1,n]$，则 Border 长度范围在该区间内的集合即为 $G(u_i,v_i)$。取 $k=\max G(u_i,v_i)$，根据性质 1，剩下的 Border 也是 $S[1,k]$ 的 Border，这就是性质 4，因此有如下推论：
推论：串 $S$ 的 Border 长度排序后可以划分成 $\mathcal O(\log \vert S\vert)$ 段，每段形成等差数列。
P4482 [BJWC2018] Border 的四种求法
给出串 $S$，多次询问，每次询问 $S[l,r]$ 的最长 Border 长度。
$n,q\le 2\times 10^5$。
唉不会，先咕着。