Border理论小记 更新于 2026/7/8 16:33:34 作者

command_block

部分图源 —— 金策 : 《字符串算法选讲》,2017

看不懂的 Border 论，写不顺的 KMP。

KMP算法

讲个笑话，当教练画了个字符串算法层级图，叫我们尽量使用“低级算法”解决问题，我发现自己不会最底层的 KMP……

作用 : 对于一个字符串 $S$ ，对于每个 $i$ 求出 $S[\_,i]$ 与 $S$ 匹配的最大长度。

就是把 $S$ 的每个前缀与自身匹配，且不能无脑重合，问最长能匹配多长。

例 : ababb

    a              ab
     ababb           ababb
匹配上了 0 位   匹配上了 0 位

   aba           abab
     ababb         ababb
匹配上了 1 位   匹配上了 2 位

ababb
     ababb
匹配上了 0 位 

怎么求呢? 回忆AC自动机的内容，发现这个最短不重合可匹配前缀就是 fail ! （手动狗头

但是 AC 自动机的正确建立方法需要补 Trie 图，这玩意就不必如此麻烦了，直接暴力跳 fail ，直到有对应出边即可。

由于跳一次fail，匹配位数必然减少，所以复杂度是均摊正确的。

然后，我们就可以在这个自动机上匹配其他的串，得到每个前缀的匹配长度，同样暴力跳 fail ，复杂度也是均摊的。

可以拿来做单串匹配，给匹配串建立自动机，求出文本串每个前缀的匹配长度。

若某个位置的匹配长度为匹配串串长，则说明完整匹配了。

• P3375 【模板】KMP字符串匹配

这题终于不是橙色而是黄色了，感天动地!

生涯第一次 1A 的 KMP /ll

#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxN 1000500
using namespace std;
void build(char *s,int len,int *fail)
{
  int p=0;
  for (int i=2;i<=len;i++){
    while(p&&s[p+1]!=s[i])p=fail[p];
    if (s[p+1]==s[i])p++;
    fail[i]=p;
  }
}
void match(char *s,char *t,int len,int *fail,int *sl)
{
  int p=0;
  for (int i=1;i<=len;i++){
    while(p&&s[p+1]!=t[i])p=fail[p];
    if (s[p+1]==t[i])p++;
    sl[i]=p;
  }
}
char s[MaxN],t[MaxN];
int tp[MaxN],sl[MaxN],len1,len2;
int main()
{
  scanf("%s%s",t+1,s+1);
  len1=strlen(s+1);len2=strlen(t+1);
  build(s,len1,tp);
  match(s,t,len2,tp,sl);
  for (int i=1;i<=len2;i++)
    if (sl[i]==len1)printf("%d\n",i-len1+1);
  for (int i=1;i<=len1;i++)
    printf("%d ",tp[i]);
  return 0;
}

• P3193 [HNOI2008]GT考试

设模式串为 $S$ ，文本串为 $T$。

首先设计一个朴素 $\rm DP$ ，设 $f[i][j]$ 为文本匹配了前缀 $i$ ，模板匹配了前缀 $j$ 的方案数 $(0\leq j< |S|)$。

我们只要把 $j=|S|$ 的情况剔除，就能够保证模式串不出现。

设 $g[i][j]$ 为已经匹配了长度 $i$ ，新加一个字符使得匹配长度变为 $j$ 的方案数。

则有转移 :

$f[i+1][j]=\sum\limits_{k=0}^{|S|-1}f[i][k]g[k][j]$

不难发现， $g$ 是由模板串唯一确定的。

而上述转移正是矩阵乘法，使用矩阵快速幂即可 $O(|S|^3\log n)$ 计算。

边界是 $f[0][0]=1$ ，所以答案是矩阵第 $0$ 行的和。

现在考虑如何算出 $g$。

枚举当前匹配的长度 $p$ 和即将添加的字符 $ch$。

• 多匹配了一位。匹配长度加一。$(ch=s[p+1])$

• 跳回某个前缀，发现能够匹配了。 (和 KMP 一样跳 $fail$)

• 失配。(跳到根发现仍然无法匹配)

这部分的复杂度是 $O(|S|^2\Sigma)$ 的。

其实就是 KMP 自动机，所以有 $O(|S|\Sigma)$ 的做法。

评测记录

• 扩展KMP（Z函数）

给出串 $S$ ，定义 $z[i]={\rm lcp}(S,s[i,n])$ 。

求 $z[1]...z[n]$ ，即 $S$ 的所有后缀与 $S$ 的 $\rm LCP$。

定义 $z[0]=0$ ，且然有 $z[1]=|S|$。接下来按照 $z[2]...z[|S|]$ 的顺序求解。

定义一个 $l$ 处的匹配段 $[l,r]$ 为 $\big[l,l+z[l]-1\big]$ ，维护右端点最靠后的匹配段 $[l,r]$。

在计算 $z[i]$ 时，显然有 $l<i$。若此时 $i<r$ ，则将 $z[i]$ 初始化为 $0$ 然后暴力扩展。

否则由 $s[1,r-l+1]=s[l,r]$ ，可以利用 $z[i-l+1]$ 的值。若 $z[i-l+1]<r-i+1$ 则表明 $z[i]=z[i-l+1]$。

否则，将 $z[i]$ 初始化为 $r-i+1$ ，然后暴力扩展 $z[i]$ 并更新 $[l,r]$。

不难发现，暴力匹配的过程中 $r$ 一直随之增大，所以总复杂度是 $O(n)$ 的。

求出 $z$ 函数之后，可以进一步求解匹配问题，方法类似，具体见代码 ：

P5410 【模板】扩展 KMP（Z 函数）

#include<algorithm>
#include<cstring>
#include<cstdio>
#define ll long long
#define MaxN 20005000
using namespace std;
void zkmp(char *a,int n,int *z)
{
  z[1]=n;
  for (int i=2,l=0,r=0;i<=n;i++){
    z[i]=(r<i) ? 0 : min(z[i-l+1],r-i+1);
    while(i+z[i]<=n&&a[i+z[i]]==a[z[i]+1])z[i]++;
    if (i+z[i]-1>r){l=i;r=i+z[i]-1;}
  }
}
void zmatch(char *a,int na,char *b,int nb,int *z,int *p)
{
  for (int i=1,l=0,r=0;i<=na;i++){
    p[i]=(r<i) ? 0 : min(z[i-l+1],r-i+1);
    while(i+p[i]<=na&&a[i+p[i]]==b[p[i]+1])p[i]++;
    if (i+p[i]-1>r){l=i;r=i+p[i]-1;}
  }
}
char a[MaxN],b[MaxN];
int z[MaxN],p[MaxN];
void calc(int *z,int n)
{
  ll ans=0;
  for (int i=1;i<=n;i++)
    ans^=1ll*i*(z[i]+1);
  printf("%lld\n",ans);
}
int main()
{
  scanf("%s%s",a+1,b+1);
  int na=strlen(a+1),nb=strlen(b+1);
  zkmp(b,nb,z);calc(z,nb);
  zmatch(a,na,b,nb,z,p);calc(p,na);
  return 0;
}

Border 的一些性质

• Border 相关的定义&约定

用 $|S|$ 表示 $S$ 的长度。若只有一个串， $n$ 一般指原串长度。 $\Sigma$ 指字符集。

$\color{blue}\text{定义:}$ $\rm Border$ : 字符串的某个前缀(非原串)，能与后缀完全匹配。

如 $S[1,m]=S[n-m+1,n]$ 则称 $S[1,m]$ 为一个 $\rm Border$。

下面会简称为 $\rm Bd$。

设 ${\rm mxBd}(S)$ 为 $S$ 的最大 $\rm Bd$ ，而 ${\rm Bd}(S)$ 为 $S$ 的 $\rm Bd$ 集合。

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

$S[1,p]$ 是 $\rm Bd\Longleftrightarrow$ $|S|-p$ 是 $S$ 的周期

若 $p|n$ 称为整周期。

• KMP 与 Border 的关系

能够发现， KMP 的 fail 数组刻画的就是各个前缀的 $\rm mxBd$。

• 求出某个串的所有 Border

当然,你也可以按照定义无脑 Hash，但是这里有个更加有理有据的作法。

• $\color{blue}\text{定理(1):}$ ${\rm Bd}(S)={\rm mxBd}(S)+{\rm Bd}({\rm mxBd}(S))$

  用人话说， $\rm mxBd$ 加上 $\rm mxBd$ 的 $\rm Bd$ 恰是原串所有的 $\rm Bd$。

  $\color{blue}\text{证明:}$

  • 右侧 $\subseteq$ 左侧 : $\rm Bd$ 的 $\rm Bd$ 是 $\rm Bd$。

    若有 $S[1,m]=S[n-m+1,n]$ 且 $S[1,m_2]=S[m-m_2+1,m]$ ,

    即 $S[1,m_2]$ 是 $S[1,m]$ 的 $\rm Bd$ ， $S[1,m]$ 是 $S[1,n]$ 的 $\rm Bd$。

    把等式连接，则有 $S[m-m_2+1,m]=S[n-m_2+1,n]$ ，所以 $S[1,m_2]$ 是 $S[1,n]$ 的 $\rm Bd$。

    如果用图来表示就很直观了 ：

    原串是 $S$ ，$A$ 是 $S$ 的 $\rm Bd$ ，$B$ 是 $A$ 的 $\rm Bd$。

    $\begin{aligned} &\qquad\qquad\qquad\qquad\boxed{\qquad\qquad B\qquad\qquad} \\&\qquad\qquad\boxed{\qquad\qquad\qquad A\qquad\qquad\qquad} \\&\boxed{\qquad\qquad\qquad\qquad S\qquad\qquad\qquad\qquad} \\&\boxed{\qquad\qquad\qquad A\qquad\qquad\qquad} \\&\boxed{\qquad\qquad B\qquad\qquad} \end{aligned}$

    显然 $B$ 也是 $S$ 的 $\rm Bd$。

  • 左侧 $\subseteq$ 右侧 : $\rm Bd$ 是 $\rm mxBd$ 的 $\rm Bd$。

    假设有 $S[1,m_2]=S[n-m_2+1,n]$ ， 且 $S[1,m]=S[n-m+1,n]$ ($m$ 代表最大的 $\rm Bd$)

    即 $S[1,m],S[1,m_2]$ 均是原串的 $\rm Bd$。

    把等式连接，则有 $S[m-m_2+1,m]=S[m-m_2+1,m]$ ，所以 $S[1,m_2]$ 是 $S[1,m]$ 的 $\rm Bd$。

    图还是那张图。

而 $\rm Bd$ 必然是原串的前缀，我们先用 KMP 求出所有前缀的 $\rm mxBd$ ，然后从 $n$ 不断跳 fail 即可得到原串的所有 Border 。

$S$ 的所有 $\rm Bd$ 长度 : $\{fail[n],fail[fail[n]]...\}$。

• P3435 [POI2006]OKR-Periods of Words

由于 $\rm Bd$ 与周期对应，题意就是求每个前缀的最小非空 $\rm Bd$。

可以暴力跳 $fail$ 查询所有 $\rm Bd$ ，发现小非空 $\rm Bd$ 即为 $fail$ 树祖先最浅非根点，加个记忆化即可。

评测记录

• P2375 [NOI2014]动物园

题意就是求每个前缀 $\leq$ 长度一半的 $\rm Bd$ 个数。

先跑个KMP,建立一棵 fail 树，问题相当于询问某个前缀 $u$ 的祖先中 $len$ 值不超过 $len[u]/2$ 的点的个数。

暴力跳fail显然不可取。

• 做法一

  注意到长度具有单调性，越往上越短。可以倍增，预处理每个点的“深度”即可得到答案。

  很不幸，这不是正解，所以需要卡常。

• 做法二

  类似 KMP 的 Build ，在 fail 上匹配自身，不同的是，若匹配长度超过 $len[u]/2$ 则停止，复杂度也是均摊 $O(n)$ 的。

模板是黄题而本题(简单小应用)是蓝题，充分体现了大多数人只是背了个板子而已 (

评测记录

• P5829 【模板】失配树

对单串建立一棵 $fail$ 树。

前面说过,某个前缀的 $\rm Bd$ 集合即为 $fail$ 树上一条到根的链。

那么两个前缀的公共 $\rm Bd$ 即为公共祖先，若要求最长，即为 $\rm LCA$。

还有，本题中 $\rm Bd$ 的定义不包括原串，若 ${\rm lca}(u,v)$ 与 $u$ 或 $v$ 重合，还需向祖先跳一步。

本题数据范围较大，若显式地建立树并递归可能会 MLE。

评测记录

• P3426 [POI2005]SZA-Template

首先，满足条件的印章一定是个 $\rm Bd$。

查看该 $\rm Bd$ 在原串中的匹配，若完整地覆盖了原串，则可行，否则不可行。

如何求匹配位置呢? 回顾KMP的方法，其实就等价于把 $\rm Bd$ 拿到自动机上匹配，若匹配长度达到总长则表明配上了。

又由于 $\rm Bd$ 是原串的前缀，我们没必要对每个 $\rm Bd$ 都匹配一次，可以直接使用原来的匹配信息(即$fail$)。

但是注意，当匹配前缀 $u$ 时，其在 $i\in[1,u]$ 的匹配长度并非 $fail[i]$ ，而是 $i$ 本身(全部匹配)。需要特判一下。

若匹配长度达到当前 $\rm Bd$ 长度，则在这里匹配上了。

于是，从小到大枚举每个 $\rm Bd$ ，设为 $B$ ，称一个前缀 $u$ 合法当且仅当 $fail[u]\geq |B|$ ，即能匹配上。

随着 $|B|$ 的增大，会逐渐删除某些位置，我们使用双向链表维护。顺便维护相邻两次匹配位置的最大差值，若$\leq|B|$ ，则该 $\rm Bd$ 可行。

评测记录

• 关于周期和匹配的一些性质

• $\text{\color{blue}定理(2) }\text{Weak Periodicity Lemma :}$

  若 $p,q$ 为 $S$ 的周期，且 $p+q\leq n$ ，则 $\gcd(p,q)$ 也是 $S$ 的周期。（简称为 $\rm WPL$）

不妨设 $p>q$ ，令 $d=p-q$。

当 $i>q$ 时，有 $s[i]=s[i-q]=s[i-q+p]=s[i+d]$

当 $i<p$ 时，有 $s[i]=s[i+p]=s[i+p-q]=s[i+d]$

而以上两种情况必然包含所有的 $i$。所以，$d$ 也是 $s$ 的周期。辗转相减即可得到 $\gcd(p,q)$。

强化版 $\text{Periodicity Lemma}$ : $p+q-\gcd(p,q)\leq n\Longrightarrow\gcd(p,q)$ 也是 $S$ 的周期。证明不会。

一般用弱化版就够了。

• $\color{blue}\text{定理(3):}$ 若 $S$ 是 $T$ 的前缀，且 $T$ 有周期 $a$ ， $S$ 有整周期 $b$ ，$b|a,\ |S|\geq a$ ，则 $T$ 也有周期 $b$。

显然成立，看图 ：

$\begin{aligned} &\boxed{\qquad\ \ \ {\color{red}|}S\qquad\ |\quad}\qquad\qquad\ \ \ \boxed{\qquad\ \ \ {\color{red}|}S\qquad\ |\quad} \\T:\ &\boxed{\qquad\qquad\qquad|\qquad\qquad\qquad|\qquad\qquad\qquad|\qquad\qquad\qquad|\qquad\qquad\cdots} \\&\qquad\qquad\qquad\ \boxed{\qquad\ \ \ {\color{red}|}S\qquad\ |\quad}\qquad\qquad\ \ \ \boxed{\qquad\ \ \ {\color{red}|}S\qquad\ |\quad} \end{aligned}$

• $\color{blue}\text{定理(4):}$ 若 $S$ 如下图匹配，则表示 $S_1∪S_2$ 有长度为 $d$ 的周期。

$\begin{aligned} &\ \boxed{\qquad\qquad\qquad\qquad T\qquad\qquad\qquad\qquad} \\&\ \boxed{\qquad\qquad\quad S_1\qquad\qquad\quad} \\&\xleftrightarrow[\quad \normalsize d\quad]{}\! \boxed{\quad\qquad\qquad S_2\qquad\quad\qquad} \end{aligned}$

$S$ 有 $|S|-d$ 的 $\rm Bd$，也即 $d$ 的周期。

由于 $S_1,S_2$ 出现位置刚好相差 $d$ ，它们的周期是重合的，所以 $S_1∪S_2$ 也有周期 $d$。

• $\color{blue}\text{定理(5):}$ 若 $2|S|\geq|T|$ ，则 $S$ 在 $T$ 中的匹配位置必为等差序列。

不妨将 $T$ 中没有被匹配覆盖到的（前后）部分去掉，这样 $T$ 中的所有位置都被 $S$ 的匹配覆盖。

显然，若匹配次数 $\leq 2$ ，必为等差数列。

下面来讨论匹配次数达到 $3$ 的情况。设第一，二次匹配间隔长度为 $d$ ，之后的某次匹配与第二次匹配的间隔为 $q$。

$\begin{aligned} &\ \boxed{\qquad\qquad\qquad\qquad\qquad T\qquad\qquad\qquad\qquad\qquad\ \ \ } \\&\ \boxed{\qquad\qquad\quad S_1\qquad\qquad\quad} \\&\xleftrightarrow[\quad\ \normalsize d\quad]{}\! \boxed{\quad\qquad\qquad S_2\qquad\quad\qquad} \\&\qquad\quad\,\,\xleftrightarrow[\qquad\quad\ \normalsize q\quad\qquad]{}\! \boxed{\quad\qquad\qquad S_x\qquad\quad\qquad} \end{aligned}$

根据 $\color{blue}\text{定理(3)}$ ， $S$ 有周期 $d,q$。

由 $2|S|\geq|T|,\ d+q+|S|=|T|$ 有 $d+q\leq|S|$ ，由 $\rm WPL$ 得 $r=\gcd(d,q)$ 也是 $S$ 的周期。

假设 $S$ 的最小周期为 $p_{\min}$ ，则有 $p\leq r\leq d$ 。若 $p_{\min}\!\not|\ r$ ，由 $\rm WPL$ 可以构造出更小的周期，所以 $p_{\min}|r|d$。

由 $\color{blue}\text{定理(4)}$ , $\color{blue}\text{定理(3)}$，可得 $S_1∪S_2$ 有周期 $p_{\min}$。

若 $p_{\min}<d$ ，则能构造出比 $S_1$ 更靠前的匹配（如下图），所以只能是 $p_{\min}=r=d$。

$\begin{aligned} S_1:\ &\boxed{\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\ \ } \\S_?:\ &\quad\ \ \,\,\boxed{\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\ \ } \\S_2:\ &\!\xleftrightarrow[\quad\ \normalsize d \quad]{}\! \boxed{\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\quad\ \ |\ \ } \end{aligned}$

由于 $\gcd(d,q)=r=d\Rightarrow d|q$ ，所有匹配的循环节都是重合的。又因为匹配覆盖了整个 $T$ ，所以 $T$ 拥有和 $S$ 一样的(最小)循环节。

$\begin{aligned} &\!\!\xleftrightarrow{\quad\ \ \normalsize d\quad} \\T:\ &\boxed{\qquad\quad|\qquad\quad|\qquad\quad|\qquad\quad|\qquad\quad|\qquad\quad|\quad} \\S_1:\ &\boxed{\qquad\quad|\qquad\quad|\qquad\quad|\quad} \\S_2:\ &\qquad\quad\,\,\boxed{\qquad\quad|\qquad\quad|\qquad\quad|\quad} \\S_3:\ &\qquad\quad\,\,\qquad\quad\,\,\boxed{\qquad\quad|\qquad\quad|\qquad\quad|\quad} \\S_4:\ &\qquad\quad\,\,\qquad\quad\,\,\qquad\quad\,\,\boxed{\qquad\quad|\qquad\quad|\qquad\quad|\quad} \end{aligned}$

现在不难发现此时的匹配一定是等差序列。

• 关于 Border 的一些性质

• $\color{blue}\text{定理(6):}$ $S$ 的长度达到 $n/2$ 的 $\rm Bd$ 长度构成一个等差序列。

设长度最大的 $\rm Bd$ 为 $n-p$ ，另一个 $\rm Bd$ 长度为 $n-q$ ，且均有 $p,q\leq n/2$。

由 $\rm WPL$ 得 $\gcd(p,q)$ 也是 $S$ 的周期，所以存在长度为 $n-\gcd(p,q)$ 的 $\rm Bd$。

根据 $n-p$ 为最长 $\rm Bd$ 的假设，要满足 $\gcd(p,q)\geq p$ 即 $p|q$。( 也就是等差了，公差为 $p$ )

整个等差序列的存在性由周期不难证明。

• $\color{blue}\text{定理(7):}$ 一个串 $S$ 的所有 $\rm Bd$ 按长度排序后,可以被划分成 $O(\log n)$ 个等差序列。

首先，将该串的长度达到 $n/2$ 的 $\rm Bd$ 划分成一个等差序列。

考虑长度达到 $n/2$ 的 $\rm Bd$ 中长度最小的 $T$。

若最小循环节 $d\leq n/4$ ，不断从最长 $\rm Bd$ 减去 $d$ 则必然有 $|T|\leq \frac{3}{4}n$ 。

若 $d>n/4$ ，则最长 $\rm Bd$ 本身就 $\leq \frac{3}{4}n$。

由 $\color{blue}\text{定理(1)}$ ，其余的 $\rm Bd$ 都是 $T$ 的 $\rm Bd$，问题缩小至原来的 $3/4$ 规模。

如此缩小， $O(\log |S|)$ 轮就结束了。实际上，有更紧凑的界 $\lceil \log_2|S|\rceil$，证明从略。

一个达到上界数量级的简易构造 ： $\begin{aligned}&\texttt{abacabadabacaba}\\&\texttt{abacaba}\\&\texttt{aba}\\&\texttt{a}\end{aligned}$

由上面的证明不难发现，这些等差序列的公差是成倍增长的，所以又有推论 ：

• 一个串 $S$ 公差 $\geq d$ 的 $\rm Bd$ 等差序列总大小是 $O(n/d)$ 的。

• $\color{green}{\bf \Delta}$ 例题 ：

• P4156 [WC2016]论战捆竹竿 | Sol

• Loj#6681. yww 与树上的回文串 | Sol

• CF1286E Fedya the Potter Strikes Back | Sol

• P5287 [HNOI2019]JOJO

显然,题目需要求的东西就是 $fail$ 的和。

由于保证相邻段字母不相同,所以只能一段段匹配,不存在一段配两段的情况。

而且,除了头和尾,其余的必须完整匹配。

考虑把每一段压缩成一个二元组。如 $\texttt{aabbbaabbaabbb}$ ,可以压缩成 $\texttt{(a,2)(b,3)(a,2)(b,2)(a,2)(b,3)}$。

压缩后的 $fail$定义为二元组字符串的 $fail$,而 $flen$ 定义为各个前缀完整匹配的 $\rm Bd$ 长度(加权的 $fail$)。

对于上例,$fail=\{0,0,1,0,1,2\};\ flen=\{0,0,2,0,2,5\}$。 注意,我们认为 $\texttt{(b,2)}$ 和 $\texttt{(b,3)}$ 不匹配。

考虑加上一个二元组 $(z,c)$ 时如何计算贡献。

首先计算出压缩后的 $flen$。

一路跳 $fail$ ,查看对应的出边 $(z',c')$ ,若 $z'=z$ ,匹配长度 $d$ 对 $c'$ 取 $\max$。最终 $d$ 的值不能超过 $c$。

最后,这一段的贡献是以 $flen$ 开始的,长度为 $d+1$ 的,公差为 $1$ 的等差数列。高斯求和即可。

然而,本题要求可持久化,每次暴力跳 $fail$ 复杂度是均摊的,可能会被卡到 $O(n^2)$。

• 做法一 : 可持久化 KMP 自动机。

  回忆我们建立 $\rm AC$ 自动机的过程,暴力跳 $fail$ 复杂度同样不对,但是我们把 $\rm AC$ 自动机补全成 $\rm Trie$ 图,做到真正的 $O(1)$ 转移,复杂度就正确了。

  类似地,我们可以预处理出每个位置的每个字符出边到达的点,称之为KMP自动机。

  在KMP自动机上,可以 $O(1)$ 转移至原来需要暴力跳 $fail$ 才能到达的位置。

  由于字符集较大,不能直接暴力写出所有转移。

  build的过程 : 相当于从上一位的 $fail$ 的某个对应出边,作为该位置的 $fail$。

  从父亲处拷贝所有转移,然后修改某一个,这可以使用可持久化线段树维护。

  然后再维护答案,对于每种字母,维护对应的匹配最长段长度。这可以直接与父亲取 $\min$。

  综上,可持久化线段树维护即可。复杂度 $O(n\log n+n\Sigma)$。

• 做法二 : Border 树。

  我们需要为 $KMP$ 寻找复杂度较为严格的做法。

  回忆 : $\rm Bd$ 的长度可以被划分成 $O(\log n)$ 个等差序列。

  我们跳 $fail$ 的过程实际上就是在遍历 $\rm Bd$ ,若当中有一串等差序列,那么中间夹着的部分一定是“循环重复”的。

  既然是重复的,那也就没必要全部查看,只需要查看最长的,然后直接跳至下一个等差序列即可。

  每次跳 $fail$ 的次数严格 $O(\log n)$ ,总跳跃次数就是严格 $O(n\log n)$ 的。

  若需要可持久化,使用可持久化数组即可。复杂度 $O(n\log^2n)$。

注意到本题并没有要求强制在线,可以将操作树离线下来,将问题转化成一系列的修改和回退操作。

最终采用做法二的离线版本,复杂度为 $O(n\log n)$。

• 最小后缀 Significant Suffixes

• $\color{blue}\text{定义:}$

  记 ${\rm suf}(S)$ 为 $S$ 的后缀集合。

  记 ${\rm minsuf}(S)$ 为 $S$ 的最小后缀。

  记 ${\rm Ssuf}(S)$ 为 $\{V\in {\rm suf}(S)\big|∃T, VT={\rm minsuf}(ST)\}$ ，意思就是说，在 $S$ 后面加一个串之后，可能称为最小后缀的后缀。即 $\rm Significant Suffixes$，简称为 $\rm Ssuf$。

• $\color{blue}\text{定理(8):}$ 对于任意两个 ${\rm Ssuf}\ U,V$ ，$|U|<|V|\Rightarrow U$ 是 $V$ 的前缀。

若 $U$ 并非 $V$ 的前缀，无论向串后面加怎样的 $T$，$UT$ 和 $VT$ 的大小关系还是由 $U,V$ 的大小关系决定。

所以 $U,V$ 只有一者有可能是 ${\rm Ssuf}$，矛盾。

注意，$U$ 同时也是 $V$ 的后缀，所以 $U$ 是 $V$ 的 $\rm Bd$。

• $\color{blue}\text{定理(9):}$ 若串 $S$ 有两个 ${\rm Ssuf}\ U,V$ 满足 $|U|<|V|$ ，则 $2|U|<|V|$

假设 $|U|<|V|<2|U|$ ，由 $\color{blue}\text{定理(8)}$ 可得 $U$ 是 $V$ 的 $\rm Bd$。

即对应长度为 $|V|-|U|<|U|,|V|/2$ 的周期。设一个周期为 $T$ ，令 $U=TC,V=TTC$。

假设在后面加了 $R$（可空） 后，有 $UR<VR$ 即 $TCR<TTCR$ ，则 $CR<TCR$ ，所以 $UR$ 注定不可能是最小后缀，矛盾。

推论 ：$|{\rm Ssuf}(S)|\leq O(\log |S|)$。

• $\color{green}{\bf \Delta}$ 例题 ：P5211 [ZJOI2017]字符串 | Sol