首页 > 代码库 > Poj 1961 KMP
Poj 1961 KMP
题意：给定一个字符串，求他每一个前缀，如果他是周期的，求len/最短循环节。
分析：
复习一下KMP，之前有详细解析。
由于朴素匹配每次移动一位，KMP可以多移动 f[i] 位，f 就是失配函数，失配函数怎么得到，是通过模式串自己匹配自己得到。
地推 f[i+1] ，如果 i+1 失配，那么先看前一个数字，他是否适合，不适合，继续向前。
本题：
应用 f，如果字符串周期，那么 他的最短循环节 可以通过 f 得到。
f[i] : 根据定义， 前缀 和后缀的最长公共长度，那么 i - f[i] 就是最短循环节。
需要注意的是，i+1，！！！（自己体会）
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 6 const int maxn = 1000000 + 5; 7 char P[maxn]; 8 int f[maxn]; 9 10 int main()11 {12 int n,kase = 1;13 while(scanf("%d",&n),n) {14 scanf("%s",P);15 f[0] = 0;f[1] = 0;16 for(int i=1;i<n;i++) {17 int j = f[i];18 while(j&&P[i]!=P[j])19 j = f[j];20 f[i+1] = (P[i] == P[j] ? j+1:0);21 }22 23 printf("Test case #%d\n",kase++);24 for(int i=2;i<=n;i++) {25 if(f[i]>0&&i%(i-f[i])==0)26 printf("%d %d\n",i,i/(i-f[i]));27 }28 puts("");29 30 }31 return 0;32 }
Poj 1961 KMP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。