Border理论小记

command_block

2020-06-10 16:38:06

Personal

部分图源 —— 金策 : 《字符串算法选讲》,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 指字符集。

如 $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$ 的周期 ![](https://cdn.luogu.com.cn/upload/image_hosting/addb8g6s.png?x-oss-process=image/resize,m_lfit,l_320) 若 $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。
&\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 。

- [P3435 [POI2006]OKR-Periods of Words](https://www.luogu.com.cn/problem/P3435) 由于 $\rm Bd$ 与周期对应，题意就是求每个前缀的最小非空 $\rm Bd$。可以暴力跳 $fail$ 查询所有 $\rm Bd$ ，发现小非空 $\rm Bd$ 即为 $fail$ 树祖先最浅非根点，加个记忆化即可。 [评测记录](https://www.luogu.com.cn/record/34508052) - [P2375 [NOI2014]动物园](https://www.luogu.com.cn/problem/P2375) 题意就是求每个前缀 $\leq$ 长度一半的 $\rm Bd$ 个数。先跑个`KMP`,建立一棵 `fail` 树，问题相当于询问某个前缀 $u$ 的祖先中 $len$ 值不超过 $len[u]/2$ 的点的个数。暴力跳`fail`显然不可取。 - 做法一注意到长度具有单调性，越往上越短。可以倍增，预处理每个点的“深度”即可得到答案。很不幸，这不是正解，所以需要卡常。 - 做法二类似 `KMP` 的 `Build` ，在 `fail` 上匹配自身，不同的是，若匹配长度超过 $len[u]/2$ 则停止，复杂度也是均摊 $O(n)$ 的。模板是黄题而本题(简单小应用)是蓝题，充分体现了大多数人只是背了个板子而已 ( [评测记录](https://www.luogu.com.cn/record/34325751) - [P5829 【模板】失配树](https://www.luogu.com.cn/problem/P5829) 对单串建立一棵 $fail$ 树。前面说过,某个前缀的 $\rm Bd$ 集合即为 $fail$ 树上一条到根的链。那么两个前缀的公共 $\rm Bd$ 即为公共祖先，若要求最长，即为 $\rm LCA$。还有，本题中 $\rm Bd$ 的定义不包括原串，若 ${\rm lca}(u,v)$ 与 $u$ 或 $v$ 重合，还需向祖先跳一步。本题数据范围较大，若显式地建立树并递归可能会 `MLE`。 [评测记录](https://www.luogu.com.cn/record/34507552) - [P3426 [POI2005]SZA-Template](https://www.luogu.com.cn/problem/P3426) 首先，满足条件的印章一定是个 $\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$ 可行。 [评测记录](https://www.luogu.com.cn/record/34508369) - **关于周期和匹配的一些性质** - $\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 的周期。证明不会。

一般用弱化版就够了。

显然成立，看图：

&\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}

&\ \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_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。

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 一样的(最小)循环节。

&\!\!\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 的一些性质

设长度最大的 \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 )

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

首先，将该串的长度达到 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) 的。
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。

若 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|)。