参考资料

https://www.luogu.com.cn/blog/command-block/border-li-lun-xiao-ji

定义

Border

$Border$ ：字符串的某个前缀（非原串），能与后缀完全匹配。

例：$S[1,m]=S[n-m+1,n]$ ，那么称 $S[1,m]$ 为 $S$ 的一个 $Border$ 。

接下来简称 $Border$ 为 $Bd$ 。

我们称 $mxBd(S)$ 为 $S$ 最长的 $Bd$ ，$Bd(S)$ 为 $S$ 的 $Bd$ 集合。

周期

若对于 $p$ ，有 $S[i]=S[i+p]$ ，称 $p$ 是 $S$ 的周期。

若 $p| |S|$ ，则称 $p$ 为整周期。

显然，$S[1,p]$ 是 $Bd$ $\Leftrightarrow$ $|S|-p$ 是周期。

与 kmp 的关系

求每个前缀的最长 Border

显然，$fail[i]$ 表示的就是 $mxBd(S[1,i])$ 的长度。

求一个串的 $Bd$ 集合。

无脑 Hash 可以，但是有个更加有理有据的做法：

$Bd(S)=\{mxBd(S)\}+Bd(mxBd(S))$

然后直接用 kmp 的 fail 指针不断跳就行了，即 $Bd(S)$ 对应了 $fail$ 树上的一条链。

性质

弱周期引理(Weak Periodicity Lemma，简称：WPL)

$p,q$ 都是 $S$ 的周期 ，且 $p+q\le |S|$ ，则 $gcd(p,q)$ 也是 $S$ 的周期。

证明：不妨假设 $p<q$ 。

$S[i]=S[i+q]=S[i+q-p],i\le n-q$

$S[i]=S[i-p]=S[i+q-p],p\le n-q<i\le n+q-p$

所以 $q-p$ 也是一个周期，辗转相减即可证明该结论。

PS：强周期定理：把条件改成 $p+q-gcd(p,q)\le n$ ，不会证明，大部分情况下用弱周期就行了，强周期了解即可。

推论：如果一个串有 $<|S|$ 的整周期，则最小周期也是整周期。

等差数列

性质 1 ：$S,T,2|S|\ge |T|$ ，则 $S$ 在 $T$ 中的出现位置构成等差数列。

证明

如果出现次数小于 $3$ 次，显然成立。

考虑第一次出现位置 $S1$ 、第二次出现位置 $S2$ 和任意一次（除了前两次）出现位置 $S3$ ，假设 $S2-S1=l1,S3-S2=l2$ 。

现在证明 $l1 | l2$ ，考虑 $S1\cup S2$ 这个字符串，显然 $l1,l2$ 都是一个周期，且 $l2\le |S|$ ，则 $l1+l2\le l1+|S|=|S1\cup S2|$ ，所以 $gcd(l1,l2)$ 也是一个周期，如果 $gcd(l1,l2)<l1$ ，则在 $S1$ 和 $S2$ 中间显然还出现了至少一次，与假设矛盾，证毕。

所以 $l1 | l2$ ，则结论显然成立 ，$l1$ 就是公差。

性质 2 ：一个字符串 $S$ 的长度 $\ge \frac{|S|}{2}$ 的 Border 构成等差数列。

证明

第一个证明方法是用周期和 Border 的等价性，然后用 WPL 很容易就能证明。

还有一个证明方法是用上面的性质 $1$ ，设 $s$ 为 $\ge \frac{|S|}{2}$ 的长度最短的 Border 。

考虑 $s$ 的所有出现位置，显然，一个 $\ge \frac{|S|}{2}$ 的 Border 对应一个 $s$ 的出现位置，只需要证明一个 $s$ 的出现位置（除了最后一个位置）也对应一个 Border 即可。

（对应方式为：除了最后一个出现位置外的出现位置，考虑这个出现位置的右端点，右端点对应的前缀就是一个 Border ，实际上，如果把原串也视作一个 border 的话，那么最后一个出现位置也有对应了）

证明方法为：观察性质 $1$ 的证明可以发现，$s$ 出现位置的公差就是 $S$ 的周期，所以显然除了最后一个位置外的每一个出现位置都对应了一个 Border 。

但是上面两个方法我还是推荐用周期进行考虑。

性质 3 ：一个字符串的 Border 从小到大排序可以划分成 $O(\log{|S|})$ 个等差数列。

证明

考虑 $\ge \frac{|S|}{2}$ 的 Border 构成等差数列，然后考虑 $<\frac{|S|}{2}$ 的最大的 Border ，显然，剩下的 Border 也是这个 Border 的 Border ，然后接着考虑就行了，所以至多 $O(\log{|S|})$ 个。

事实上，通过上面的描述，不难发现：

长度在 $(\frac{|S|}{2},|S|],(\frac{|S|}{4},\frac{|S|}{2}],(\frac{|S|}{8},\frac{|S|}{4}],(\frac{|S|}{16},\frac{|S|}{8}]…$ 即 $(\frac{|S|}{2^{k+1}},\frac{|S|}{2^k}]$ 的 Border 构成等差数列。

或者长度在 $[1,2),[2,4),…,[2^i,2^{i+1}),[2^{i+1},|S|]$ 的 Border 也构成等差数列。（ $|S|<2^{i+2}$ ）

显然，长度在 $a,b$ 的 Border 都构成等差数列。

失配树

对于一个串，考虑对于每个前缀建立一个节点，其父亲是其的 $mxBd$ ，这样构成的一棵根为空串的树叫做失配树，显然，Kmp 的 fail 数组就代表了这棵树。

这棵树有很多性质。

性质 1 ：根据 $Bd(S)=\{mxBd(S)\}+Bd(mxBd(S))$ 可以得出，一个前缀的所有 Bd 就是到父亲的这条链。

这个性质可以用于解决这个题目：

https://www.luogu.com.cn/problem/P5829

题目大意：给一个串，$q$ 次询问，每次询问询问两个前缀的最长公共 border 长度。

显然就是失配树上找 LCA 就行了。

性质 2 ：每个点到根节点的路径可以划分成 $O(\log)$ 段，每段父子间长度差恒定。（也就是上面 $O(\log)$ 段等差数列的失配树版本）

这个性质可以产生上面那道题目的另外一个做法：

做法

首先，先介绍一种常数更加小的划分 Border 的方式：

如果 $2fail[x]\ge x$ ，令 $p=x-fail[x]$ ，那么 $x$ 到 $x\mod {p}+p$ 构成等差数列，否则 $x$ 自己就是个等差数列。

然后令 $x$ 跳到最大的没有被划分进等差数列的位置就行了，实操中当 $2fail[x]\ge x$ 时，往往直接跳到 $x\mod {p}+p$ ，即认为等差数列间可以有交叉，这样处理方便一些，而且显然，不难证明这么跳 $x’<\frac{2x}{3}$ ，所以仍然是 $O(\log)$ 段。

（这个划分方式还有个小性质，如果 $2fail[x]\ge x$ ，则等差数列至少有两项，否则只有一项）

在划分完 Border 后，显然可以用扩展欧几里得去处理，但是这样是两个 $\log$ 的，而且写起来还没 LCA 好写。

考虑利用性质进行优化，现在考虑找 $x,y$ 前缀的最长公共 Bd ，不妨认为原串也算 Bd，且 $x>y$ ，考虑上述划分中 $x$ 的第一个等差数列。

如果 $2fail[x]<x$，那么显然 $x=fail[x]$ 即可。

如果 $2fail[x]\ge x$ ，那么显然如果 $x\equiv y\mod p$ ，则 $y$ 就是最长公共 Bd ，否则考虑 $y$ 的长度：

  1. 如果 $y<2p$ ，那么显然这个等差数列，也就是分配树上的这条链除了链头没有别的串可能是公共 Bd 。
  2. 如果 $y\ge 2p$ ，显然 $y$ 的最小周期也是 $p$ ，则根据 WPL 可以得出链上 $\ge 2p$ 的点都不可能是公共 Bd（考虑 $x,y$ $\ge 2p$ 的所有 Bd ，显然互不相同），也即只有链头还有可能成为答案，所以 $x=x\mod p+p$。

不难发现，这个做法的复杂度与 $x,y$ 按照上述方法划分的等差数列个数同阶（因为上面的过程其实就是从一个等差数列的列尾，跳到下一个等差数列的列尾），也就是 $O(n+q\log{n})$ ，而且显然好写很多，空间也只用 $O(n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char st[N];
int fail[N],n,q;
int main(){
    scanf("%s",st+1);n=strlen(st+1);

    fail[0]=-1;int now=0;
    for(int i=2;i<=n;i++){
        while(now!=-1 && st[now+1]!=st[i])now=fail[now];
        fail[i]=++now;
    }
    
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        int x,y;scanf("%d%d",&x,&y);
        x=fail[x];y=fail[y];
        while(x!=y){
            if(x<y)swap(x,y);
            if(fail[x]*2<x)x=fail[x];
            else{
                assert(x);
                int d=x-fail[x];
                if(x%d==y%d)x=y;
                else x=x%d+d;
            }
        }
        printf("%d\n",x);
    }
    return 0;
}

一些其他性质

  1. 如果一个串 $S$ 有 $\ge \frac{|S|}{2}$ 的 Border，则最小的 $\ge \frac{|S|}{2}$ 的 Border 长度 $<\frac{3|S|}{4}$ 。

    证明

    假如最小周期 $p\le \frac{|S|}{4}$ ，则显然 Border $\ge \frac{3|S|}{4}$ 时，还能再去掉一个周期，直到 $<\frac{3|S|}{4}$ 。

    假如 $>$ ，显然所有的 Border 都 $<\frac{3|S|}{4}$ ，所以也显然成立。

    证毕。

  2. 如果一个串 $s$ 有一个 $t$ 作为 mxBd ，且 $2|t|\ge|s|$ ，那么 $t$ 在 $s$ 中只出现了两次。

    证明

    由性质 $1$ 知道出现位置是等差数列，如果出现 $3$ 次及以上可以构造出更长的 Bd ，矛盾。

    这个证法和性质 2 的证明 2 挺像的，都是利用了某个 Bd 的出现位置和一些 Bd 的对应关系。

    这个性质可以应用在某些 Bd 优化题中，以确定 mxBd 上次出现的位置。