前言
KMP是一个普及度很高的字符串算法。在NOI2014与NOIP2020中均有考察。同时，上述题目均在一定程度上考察了字符串的周期这个点。本文将探讨字符串的周期。
因笔者能力有限，本文讲述的并不会很深，也不会非常简洁，而是致力于达到可以理解并应用的层面。如果您需要更深层次的探讨或是简洁的概述，可在“鸣谢”栏中继续寻找资料。同时，由于本文将大量运用KMP算法，在阅读本文前，您需要先学习KMP算法。
本文正在施工中，敬请谅解（不保证不咕）
定义
以下字符串的长度将用(|S|)表示，子串将使用(S_{l..r})的形式表示。字符串下标从1开始
我们定义一个字符串S的border为若(S_{1..x}=S_{|S|-x+1,|S|} x
eq |S|)，则(S_{1..x})为(S)的border。
概述
Q：这玩意看似与KMP无关啊
A：先回忆KMP中，我们用的(next)数组（亦称(fail)数组，下文统一用(fail)数组表示）的定义，还记得吗？
对于字符串(S)的前(i)个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作(next[i])。
——【NOI2014】动物园
所以，它就是最大border。
现在我们来解决一个问题：求(S)的每个子串的最大border。（题目来源：Luogu P3435 [POI2006]OKR-Periods of Words）那其实就是(fail)数组的和了。
全文完
别急，border有不少性质，下文中我们将讲解。
题目讲解
Luogu P5829 【模板】失配树
题目大意：求字符串(S)中 ([1..p] [1..q])的最长公共border
题目思路：
首先，(fail_{fail_i})一定是([1,fail_i])的border。又因(fail_i)是([1..i])的border，那么([1..fail_{fail_i}])是([1..i])的border。读者可自行理解。
那么，fail数组实际构成了一棵树，任意节点的父亲节点均是其border，那么我们跑LCA即可。
事实上，这颗树我们没有必要建出来，否则会引起空间浪费。
代码：
#include<bits/stdc++.h>
using namespace std;
char st[1090000];int f[1001000],dep[1001000],fa[21][1001000],m,u,v;
long long fain()
{
long long s=0;char ch;
while (1)
{
ch=getchar();
if (ch>='0'&&ch<='9') break;
}
s=ch-'0';
while (1)
{
ch=getchar();
if (ch<'0'||ch>'9') return s; else s=s*10+ch-'0';
}
return s;
}
int main()
{
int len=0;
while (1)
{
st[++len]=getchar();
if (st[len]<'a'||st[len]>'z') break;
}
f[1]=0;
for (int i=2,j=0;i<len;i++)
{
while (st[i]!=st[j+1]&&j!=0) j=f[j];
if (st[i]==st[j+1]) j++,f[i]=j,dep[i]=dep[j]+1;else f[i]=0,dep[i]=0;
fa[0][i]=f[i];
for (int k=1;k<=20;k++)
fa[k][i]=fa[k-1][fa[k-1][i]];
}
m=fain();
for (int i=1;i<=m;i++)
{
u=fain();v=fain();
if (dep[u]>dep[v]) swap(u,v);
if (u==v) {cout<<f[u]<<endl;continue;}
for (int j=20;j>=0;j--)
if (dep[fa[j][v]]>=dep[u]) v=fa[j][v];
if (u==v) {cout<<f[u]<<endl;continue;}
for (int j=20;j>=0;j--)
if (fa[j][u]!=fa[j][v]) u=fa[j][u],v=fa[j][v];
if (fa[0][u]==fa[0][v])
cout<<fa[0][u]<<endl;
}
return 0;
}
Luogu P2375 【NOI2014】动物园
题目大意：
现在求一个(num)数组，定义为对于字符串(S)的前(i)个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作(num[i])。
输出(num_i+1)的乘积。
多组（(le 5)）数据，字符串长度(le 1 imes 10 ^6)
题目思路：
暴力KMP,50分。
不难发现，对于节点(x)，若(y)是合法的，那么y的border也是合法的。
考虑KMP的过程中，将当前位置与(fail_i)连边，会形成一棵树。那么我们可以在这棵树上通过树上倍增找到最深的合法的节点，则该节点的父亲均合法。
复杂度(T imes NlogN)，理论上应该能过。但很遗憾，T了。
考虑快读+数组维度优化，Luogu (100) UOJ (90) LOJ (100)
代码：
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int t,f[1000100],fa[22][1000100],cnt[1000100],mi[21];char st[1000100];
int main()
{
t=int(getchar()-'0');getchar();
mi[0]=1;
for (int i=1;i<=20;i++)
mi[i]=mi[i-1]*2;
for (int tt=1;tt<=t;tt++)
{
int len=1;
st[1]=getchar();
if (st[1]<'a'||st[1]>'z') {cout<<"1
";continue;}
f[1]=0;cnt[1]=0;
for (int i=2,j=0;;i++)
{
len++;
st[i]=getchar();
if (st[i]<'a'||st[i]>'z') {len--;break;}
while (st[i]!=st[j+1]&&j)
j=f[j];
if (st[i]==st[j+1]) f[i]=j+1,j++,cnt[i]=cnt[j]+1;else f[i]=0,cnt[i]=0;
bool flag=true;
if (f[i]) fa[0][i]=f[i];else fa[0][i]=0,flag=false;
for (int k=1;mi[k]<=i;k++)
fa[k][i]=fa[k-1][fa[k-1][i]];
}
long long ans=1;
for (int i=2,sm=0;i<=len;i++)
{
int s=1,k=i;
if (i>mi[sm]) sm++;
for (int j=sm;j>=0;j--)
if ((f[fa[j][k]]<<1)>i) k=fa[j][k];
if ((f[k]<<1)>i)
{
if ((f[fa[0][k]]<<1)<=i) k=fa[0][k]; else continue;
}
s+=cnt[k];
ans*=s;
ans%=mod;
}
printf("%lld
",ans);
}
return 0;
}
正解是用dfs，有兴趣的可自行寻找资料。
鸣谢
1.本文大量参考自@command-block的相关博客