本文主要是介绍字符串匹配 KMP算法，BF算法，Sunday算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：AcWing141. 周期
一个字符串的前缀是从第一个字符开始的连续若干个字符，例如 abaab 共有 5 个前缀，分别是 a，ab，aba，abaa，abaab。
我们希望知道一个 NN位字符串 S 的前缀是否具有循环节。
换言之，对于每一个从头开始的长度为 i（i>1）的前缀，是否由重复出现的子串 A 组成，即 AAA…A （A 重复出现 K 次,K>1）。
如果存在，请找出最短的循环节对应的 K 值（也就是这个前缀串的所有可能重复节中，最大的 K 值）。
输入格式
输入包括多组测试数据，每组测试数据包括两行。
第一行输入字符串 S 的长度N。
第二行输入字符串 S。
输入数据以只包括一个 0 的行作为结尾。
输出格式
对于每组测试数据，第一行输出 Test case # 和测试数据的编号。
接下来的每一行，输出具有循环节的前缀的长度 i 和其对应K，中间用一个空格隔开。
前缀长度需要升序排列。
在每组测试数据的最后输出一个空行。
数据范围
2≤N≤1000000
输入样例：
3
aaa
4
abcd
12
aabaabaabaab
0
输出样例：
Test case #1
2 2
3 3Test case #2Test case #3
2 2
6 2
9 3
12 4
知识：
（1）KMP算法能够在线性时间内判定字符串A[1-N]是否是字符串B[1-N]的子串，并求出A在B中各次出现的位置，非常优秀！
!!!KMP算法详细介绍：https://www.cnblogs.com/zzuuoo666/p/9028287.html
//KMP算法next数组的求法
next[1]=0;//初始化next[1]和j为0
for(int i=2,j=0;i<=n;i++){while(j>0&&a[i]!=a[j+1]) j=next[j];//如果扩展失败，令j变为next[j],直至j变为0（应该重新从头开始匹配） if(a[i]==a[j+1]) j++;//如果能够扩展成功，匹配长度j就增加1 next[i]=j;//next[i]的值就是j
}//KMP算法f数组的求法
for(int i=1,j=0;i<=m;i++){while(j>0&&(j==n||b[i]!=a[j+1])) j=next[j];if(b[j]==a[j+1]) j++;f[i]=j;
}思路：先对字符串进行自匹配求出next数组，当i%(i-next[i])==0时，s[1~i-next[i]]就是s[1~i]的最小循环元。以此类推，若i%(i-next[next[i]])==0时,s[1~i-next[next[i]]就是s[1~i]的次小循环元。并且一个字符串的任意循环元的长度必然是最小循环元长度的倍数。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
char a[N];
int ne[N],n,t;
void cal_ne(){ne[1]=0;for(int i=2,j=0;i<=n;i++){while(j>0&&a[i]!=a[j+1]) j=ne[j];if(a[i]==a[j+1]) j++;ne[i]=j;}
}
int main(){while(cin>>n&&n){scanf("%s",a+1);cal_ne();printf("Test case #%d\n",++t);for(int i=2;i<=n;i++){if(i%(i-ne[i])==0&&i/(i-ne[i])>1){printf("%d %d\n",i,i/(i-ne[i]));}} puts("");//换行}return 0;
}（2）BM算法：
https://blog.csdn.net/qq_21201267/article/details/92799488
（3）Sunday算法：
https://blog.csdn.net/q547550831/article/details/51860017
这篇关于字符串匹配 KMP算法，BF算法，Sunday算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
