没错，博主又开始学算法了。。。话说我以前不是叫自己猴子吗？
平常我们字符串匹配，暴力\(O(nm)\)是不是感觉自己已经可以称霸全世界了？
不是！还有STL
STL的大佬就不要看我这种蒟蒻的博客了。
当然，时间慢自然会有大佬去开发一种算法来加速。
就是他们，研究出了kmp看毛片算法。
sto,sto,sto
kmp的思想是什么?
建一个kmp数组，\(kmp_{i}\)代表在一个字符串中\([i-kmp_{i}+1,i]\)与\([1,kmp_{i}]\)是匹配的。（注意，\(kmp_{i}\ne i\)）。
那么，当我们知道了\(kmp_{i}\)如何求出\(kmp_{i+1}\)？
（设字符串为\(ss\)数组）
匹配过程：
最后我们就匹配成功了。
所以，当\(ss[kmp_{i}+1]\ne ss[i+1]\)时，我们可以设\(now=kmp_{i}\)
然后不断匹配，匹配不成功就让\(now=kmp_{now}\)，我们可以设\(kmp_{0}=-1\)当\(ss[kmp_{i}+1]=ss[i+1]\)或\(now=-1\)时退出，同时用\(kmp_{i+1}=now+1\)。
其实第一个也可以这么做，因为当\(now=kmp_{i}\)时就已经退出了，所以\(kmp_{i+1}=now+1=kmp_{i}+1\)。
我们可以先处理出子串的kmp数组，那么怎么做？
设\(i\)为当前已经匹配到的母串的位置，那么设now代表母串中\([i-now+1,now]\)与子串的\([1,now]\)完全匹配，那么的话，就像建立kmp数组那样，以母串的第\(i\)个位置now来处理出\(i+1\)的位置的now。
至于具体过程，跟处理kmp数组那样，换汤不换药，自己想。
就是你懒！
而这里，就是判断当\(now=\)子串的长度时，\(ans++,now=0\)。
注：这里的kmp数组许多人都失败\((fail)\)数组。
注意，不能让\(kmp_{i}=i\)
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
char s1[2100],s2[2100];//字符串
int kmp[2100],ans,n,m;//kmp数组
int main()
{
while(1)
{
scanf("%s",s1+1);n=strlen(s1+1);
if(n==1 && s1[1]==‘#‘)break;//判断
scanf("%s",s2+1);m=strlen(s2+1);//输入
kmp[0]=-1;ans=0;//一种让kmp[i]!=i的方法
int now;
for(int i=1;i<=m;i++)//子串
{
now=kmp[i-1];
while(now>-1 && s2[i]!=s2[now+1])now=kmp[now];
kmp[i]=now+1;
}
now=0;
for(int i=1;i<=n;i++)//母串匹配
{
while(now>-1 && s1[i]!=s2[now+1])now=kmp[now];
now++;
if(now==m)ans++,now=0;//统计答案
}
printf("%d\n",ans);
}
return 0;
}这道题，用kmp做的话，仔细观察，发现如果\(n\bmod (n-kmp_{n})==0\)，那么\(n-kmp_{n}\)就是循环节，否则不存在循环节。
Why?
首先，如果\(kmp_{n}<(n+1)/2\)那么\(n\bmod (n-kmp_{n})\ne 0\)
因此我们不讨论这种情况。
如图：
注：这里a1-a10代表字符串的前缀，b1-b10是字符串的后缀
那我们现在需要证明当\(n\bmod (n-kmp_{n})\ne 0\)时没有循环节。
反证法：
如果有，设循环节长度为\(k\)，然后设\(kmp_{n}\%k=tt\)。
那么：
所以这种方法可以行得通，耶！
代码：
#include<cstdio>
#include<cstring>
using namespace std;
char ss[2100000];
int kmp[2100000],n;
int main()
{
while(1)
{
scanf("%s",ss+1);n=strlen(ss+1);
if(n==1 && ss[1]==‘.‘)break;//判断
kmp[0]=-1;
int now=0;
for(int i=1;i<=n;i++)//建造kmp数组
{
now=kmp[i-1];
while(now>-1 && ss[now+1]!=ss[i])now=kmp[now];
kmp[i]=now+1;
}
if(n%(n-kmp[n])==0)printf("%d\n",n/(n-kmp[n]));//判断
else printf("1\n");
}
return 0;
}这道题，我们这次只要输出n-kmp[n]就行了。。。
首先在这道题中，如果abc是循环节，那么bca、cab也是循环节，也就是谁从开头求循环节或从结尾求循环节得出的长度是一样的，那么像上次那样\(n-kmp_{n}\)？
答案是肯定的，假设从结尾求得循环节是\(a_{1}a_{2}a_{3}...a_{k}\)而字符串则是\(a_{i}a_{i+1}...a_{k}a_{1}a_{2}...a_{k}...\)。那么\(kmp_{n}\)除了像上次那样统计了循环节外，还统计了开头\(a_{i}a_{i+1}...a_{k}\)的部分，所以拿\(n-kmp_{n}\)刚好就是循环节的长度，而且因为题意，我们不用担心无解的情况，直接输出就好了。
#include<cstdio>
#include<cstring>
using namespace std;
int kmp[1100000],n;
char st[1100000];
int main()
{
scanf("%d",&n);
scanf("%s",st+1);
kmp[0]=-1;
for(int i=1;i<=n;i++)//统计kmp数组
{
int now=kmp[i-1];
while(now!=-1 && st[i]!=st[now+1])now=kmp[now];
kmp[i]=now+1;
}
printf("%d\n",n-kmp[n]);//输出
return 0;
}将题意转成人话：
求字符串A的所有前缀AA，定义最长的不断复制自己再接到后面能够覆盖前缀AA且不等于AA的字符串为AA的周期（周期可以是空串），如abababab，ababab通过不断复制自己再接到后面形成abababababab...能够覆盖abababab，且ababab的长度是最长的，求所有前缀AA的周期长度总和。
这道题，就是要我们求出每个前缀的最长循环节，跟上题差不多，不过找的方式变了。
从前往后找与从后往前找的最长循环节长度一样。
那么我们考虑题意是接到不断复制接到前面，那么我们可以知道
而且通过上一道题，我们可以知道，这里的红色块就是上一道题的循环节，而循环节就是\(now-kmp_{now}\)，我们就可以不断用\(now\%(now-kmp_{now})\)来处理出黄色块的长度，然后用前缀AA的长度减去黄色块的长度，就是最长循环节的长度了。
当然也有细节：
优化：当\(kmp_{i}\ne 0\)时，我们可以用\(kmp_{i}=前缀1->i的黄色块的长度\)，省去以后找的次数。
#include<cstdio>
#include<cstring>
using namespace std;
int kmp[1100000],n;
char st[1100000];
int main()
{
scanf("%d",&n);
scanf("%s",st+1);
kmp[0]=-1;
for(int i=1;i<=n;i++)//kmp
{
int now=kmp[i-1];
while(now!=-1 && st[i]!=st[now+1])now=kmp[now];
kmp[i]=now+1;
}
long long ans=0;
for(int i=1;i<=n;i++)
{
int now=i;
while(kmp[now])//处理黄色块的长度
{
int gtk=kmp[now];
now%=gtk;
if(now==0)now=gtk;//特判
}
if(kmp[i]!=0)kmp[i]=now;//优化
ans+=i-now;//统计
}
printf("%lld\n",ans);//输出
return 0;
}当然，有的大佬为了让过程简洁，用另一种方法，思想一样，方法不同。
每次跳\(kmp_{now}\)，当\(kmp_{now}=0\)时退出，至于为什么正确，参考上面的题目与kmp数组的定义。
优化也可以用到哟。
#include<cstdio>
#include<cstring>
using namespace std;
int kmp[1100000],n;
char st[1100000];
int main()
{
scanf("%d",&n);
scanf("%s",st+1);
kmp[0]=-1;
for(int i=1;i<=n;i++)//kmp数组处理
{
int now=kmp[i-1];
while(now!=-1 && st[i]!=st[now+1])now=kmp[now];
kmp[i]=now+1;
}
long long ans=0;
for(int i=1;i<=n;i++)
{
int now=i;
while(kmp[now])now=kmp[now];//找到黄色块的长度
if(kmp[i]!=0)kmp[i]=now;
ans+=i-now;//统计答案。
}
printf("%lld\n",ans);//输出
return 0;
}人话。。。
统计字符串中由A+B+A构成的字符子串的个数，且|A|≥k，|B|≥1，且一个划分不同但区域相同的算同一子串。
如aaaaa，可以分成A="aa"，B="a"或A="a"，B="aaa"，但是只算一个。
枚举左端点，跑左端点至n的kmp，然后暴力枚举右端点，\(O(n^{2})\)可以过！
不过如何判断一个区间是否符合？
设\(now=kmp_{r}\)，然后判断l->now的长度符不符合要求，不符合继续让\(now=kmp_{now}\)，符合，统计答案，退出。
可能说的不好。。。看代码然后自行理解。
#include<cstdio>
#include<cstring>
using namespace std;
int kmp[21000],n,m,ans;
char st[21000];
int main()
{
scanf("%s",st+1);n=strlen(st+1);//输入
scanf("%d",&m);
for(int i=1;i<=n;i++)
{
kmp[i-1]=i-2;//像kmp[0]=-1的操作
for(int j=i;j<=n;j++)
{
int now=kmp[j-1];
while(now!=i-2 && st[now+1]!=st[j])now=kmp[now];//处理kmp数组
kmp[j]=++now;now=j;
if(i+2*m<=j)//i+2*m-1+1，先判断可不可能存在这样的子串
{
while(kmp[now]>=i+m-1)//判断条件
{
if(kmp[now]<=(i+j)/2-1)//判断是否是A+B+A的形式
{
ans++;//统计，退出
break;
}
now=kmp[now];//继续判断
}
}
}
}
printf("%d\n",ans);//输出
return 0;
}一个栈储存目前没有被删除的字符串，然后。。。
#include<cstdio>
#include<cstring>
using namespace std;
char s1[1100000]/*母串*/,s2[1100000]/*子串*/,st[1100000]/*栈*/;//字符串
int kmp[1100000],dt[1100000],n,m,len;//kmp数组
int main()
{
scanf("%s%s",s1+1,s2+1);n=strlen(s1+1);m=strlen(s2+1);//输入
kmp[0]=-1;//
for(int i=1;i<=m;i++)
{
int now=kmp[i-1];
while(now!=-1 && s2[i]!=s2[now+1])now=kmp[now];
kmp[i]=now+1;
}//处理kmp数组
for(int i=1;i<=n;i++)
{
st[++len]=s1[i];//弹入栈
int now=dt[len-1];
while(now!=-1 && st[len]!=s2[now+1])now=kmp[now];
dt[len]=now+1;//记录
if(dt[len]==m)len-=m;//如果是可以匹配，弹出
}
for(int i=1;i<=len;i++)printf("%c",st[i]);//输出
printf("\n");
return 0;
}终于写完了。。。
原文：https://www.cnblogs.com/zhangjianjunab/p/9954687.html