若您发现本文有什么错误，请联系我，我会及时改正的，谢谢您的合作！
本文为原创文章，转载请注明出处
本文链接 ：http://www.cnblogs.com/Yan-C/p/3792015.html
今天呢 ，再次在KMP里徜徉了一次，又有了一点点的深入啊。学习就是要这样一次一次的循环一次次的深入。
以前都是看了别人的博客，会了能够做题的就会算了，题解也不会写，别人的博客也不转，就这样算了。今天趁着激情＋嗨，好好的写一下KMP吧。
关于字符串的匹配，还有最小循环节等问题都是可以用KMP解决的，虽然有时数据水点可以暴力，砰砰砰，for循环干倒，但是咱们是文化人，不能这么暴力的。
蛋就扯到这了，暴力的就自己研究吧。
我们先说一下为什么要学习KMP呢，因为用得到啊。前一句删掉，说废话了，因为这个KMP是线性级的，很厉害吧，字符匹配线性级的。
你 想想：假如你是子串，你的女神就在主串中，然后很多小伙伴都要找到这个女神，然后去麻辣烫，啪啪啪。如果其他小伙伴都比较暴力，双重for循环去找女神， 你想想多慢N^2啊，女神那时候早饿了，谁会找啊是不是？如果你用KMP，嗖嗖嗖，一会就找到了女神，女神一看你这速度，三秒啊（传说中的三秒男）。肯定 就跟你走了是不是？那你就抱的女神归了，那还不学这个算法。
下面开始将正题。
这篇博文共分4个部分，依个人口味看部分。（一） 求next[]（二）next[] 数组的解释（三） 利用next[] 进行匹配（四） KMP的应用。
（一） 求next[]
先说明一下 在我求的next[]中 next[0]=-1的。
下面先看一下next[] 的求法。
next[] 的求法呢很简单就是几句话的事，不信是不？是不是不信？，这么厉害的算法，就几句话的事？答案是：是的。
未优化版：
void getnext(char *s) { int next[81]={-1,0}; int i=0,j=-1,l=strlen(s); while(i<l) if(j==-1||s[i]==s[j]) s[++i]=++j; else j=next[j]; }
怎么样傻了吧，就这么简单，嘿嘿，对了但是不完全，不完全？对啊，因为你没看到这只是求了一个next[] 吗！
这就是KMP的第一步，也是最重要的一步。求next[]。这个是没有优化的。
现在再写一个优化版的，其实只是让后面的next[]的值 变得小一点。
优化版来喽：
void getnext(char *s) { int next[81]={-1,0}; int i=0,j=-1,l=strlen(s); while(i<l) if(j==-1||s[i]==s[j]){ i++; j++; if(s[i]==s[j]) next[i]=next[j]; else next[i]=j; //next[i]=s[i]==s[j]?next[j]:j; } else j=next[j]; }
优化版奉上，希望您笑纳。加了一个if else 还是很短对吧？这次知道什么叫短小精悍了吧。
好了 next[] 会求了吧？ 不会咱们继续。
（二）next[] 数组的解释
借鉴 http://blog.sina.com.cn/s/blog_96ea9c6f01016l6r.html
这个部分就是大部分人刚刚学KMP的疑惑了。
我们来看几个例子。
用未优化的版本吧，毕竟代码更短，（更强，更持久）是我们的口号嘛。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <windows.h>
void getnext(char *s)
{
int next[81]={-1,0};
int i=0,j=-1,l=strlen(s);
while(i<l)
if(j==-1||s[i]==s[j])
next[++i]=++j;
else
j=next[j];
system("CLS");
for(i=0;i<l;i++)
printf("%4c",s[i]);
printf("
");
for(i=0;i<=l;i++)
printf("%4d",next[i]);
printf("
");
}
int main(void)
{
char s[81];
scanf("%s",s);
getnext(s);
return 0;
}
No.1
字符串是 ：ababc
0 1 2 3 4 这是位序，也就是s[i] 中的i。
a b a b c 这个就是s[i] 了。
让我们来跟着程序走一遍 看看我们是不是能正确的走出next[] 的值呢
0 1 2 3 4
a b a b c
-1 0 0 1 2 这就是我猜的next[] 的值(其实第一遍错了，又改了，嘿嘿，反正你看不到我在这出糗)，你的是多少呢？咱们来运行一下程序看一下对不对。毕竟小平爷爷说过，实践是检验真理的唯一标准——by 小平爷爷。
我写的程序是这个样子的。
嘿嘿 一样吧。我厉害吧，哎不对怎么多了一个 0呢，去掉这个0就跟我的猜想一样了。这个0先不急咱们慢慢来，不要急嘛，你说对吧。心急吃不了热豆腐。
开始讲解喽，注意哦，认真听，先别看美女了。
0 1 2 3 4
a b a b c
-1 0 0 1 2
我们这样看 ：
next[0]=-1 是我们预先设定的，所以它不会变。
第1位next[1]=0;
然后以后的每一位都需要前一位来确定了。
第2位的a怎么确定next[] 值呢，第2位的前一位为1，用第1位的b与b的next[]值为位序的那个字母比较，如果两个字符相等就在b的基础上+1，不然的话就是b的值了。在第1位上的b与其next[] 对应的值的第next[]位=a不想等，所以a的next[]为b的next[];
第3位的b，前一位对应的字符为a,a的next[]的位序上的字符为a,所以b的next[]在a 的next[] 基础上+1。
第4位的c，前一位对应的字符为b,b的next[]的位序上的字符为b,所以c的next[]在b的next[] 基础上+1。
不知道大家是不是看懂点了？下面加上了next[位序]，s[位序]说的，希望这次没看懂的童鞋，能看懂吧，阿门。
No.2
字符串为 : aaaaab
0 1 2 3 4 5
a a a a a b
-1 0 1 2 3 4
又对了，真棒。这个0 同样不管。
我们来看，这个例子。
next[0]=-1;
next[1]=0;
以后的每一位都需要靠前一位来确定。
s[2]=a的前一位为s[1]=a,next[1]=0,因为s[next[1]=0]=a,与s[1]相同，所以next[2]=next[1]+1=1;
s[3]=a的前一位为s[2]=a,next[2]=1,因为s[next[2]=1]=a,与s[2]相同，所以next[3]=next[2]+1=2;
s[4]=a的前一位为s[3]=a,next[3]=2,因为s[next[3]=2]=a,与s[3]相同，所以next[4]=next[3]+1=3;
s[5]=b的前一位为s[4]=a,next[4]=3,因为s[next[4]=3]=a,与s[4]相同，所以next[5]=next[4]+1=4;
就是这个样子，同学们有没有明白呢？
好吧，我们再讲一个
No.3
字符串为 ： powwop
0 1 2 3 4 5
p o w w o p
-1 0 0 0 0 0 1
这次又对了，不对啊，最后面的那个怎么变1了呢？相信跟多同学都已经知道最后一位跟前面的字符一样确定其next[] 的，只是写者没说而已，下面咱们还有用处哦。
咱们开始No.3的讲解。
next[0]=-1;
next[1]=0;
s[2]=w的前一位是s[1]=o,next[1]=0,因为s[next[1]=0]=p与s[1]=o不相等，所以next[2]=next[1]=0;
s[3]=w的前一位是s[2]=w,next[2]=0,因为s[next[2]=0]=p与s[2]=w不相等，所以next[3]=next[2]=0;
s[4]=o的前一位是s[3]=w,next[3]=0,因为s[next[3]=0]=p与s[3]=w不相等，所以next[4]=next[3]=0;
s[5]=p的前一位是s[4]=o,next[4]=0,因为s[next[4]=0]=p与s[4]=o不相等，所以next[5]=next[4]=0;
s[6]=' '的前一位是s[5]=p,next[5]=0,因为s[next[5]=0]=p与s[5]=p相等，所以next[6]=next[5]+1=1;
到这里就讲这些next[] 的解释了，如果还是不懂的话，可以联系我哦，嘿嘿。
（三） 利用next[] 进行匹配
说了那么多的废话，唾液横飞啊。以上都是屌丝的准备环节，接下来就是振奋人心的时候了，快速的配对女神，哦哈哈。想想都有点小兴奋。
在这里我将配对的函数代码贴上，然后对大家说一下下，就滑滑梯（换话题，下一模块），毕竟这么振奋人心的事情，谁都不愿浪费时间嘛，自己的女神当然是自己****。嘿嘿。
void getnvshen() { int i=0,j=0; int len1=strlen(str); int len2=strlen(s); while(i<len1&&j<len2) if(j==-1||str[i]==s[j]) i++,j++; else j=next[j]; if(j==len2) printf("Yes "); else printf("No "); }
当你与女神能匹配就输出Yes，不然就No喽。
这个匹配就是尽可能的拉大移动的距离，就像这样
你用暴力如果遇到不一样的就只能从j==0开始
j————>0，这就是暴力的匹配。
j——————————————————————————————————————>10086就是KMP做的，就是这个样子，其实没这么夸张了。嘿嘿
只是j————————>max 让j尽可能的大，让它走的多，因为看到女神可定跑的快啊。
在这里给大家布置一个小小的作业，KMP都学的差不多了，肯定迫不及待的想证明一下自己的能力吧。
那么做做这个题吧，小试一下牛刀。
一位学长为了我们学KMP而出的题。
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2772
#include<stdio.h> #include<stdlib.h> #include<string.h> char s1[1000003],s2[1000003]; int next[1000003]; int main() { int i,j,l1,l2; while(~scanf("%s",s1)){ scanf("%s",s2); l1=strlen(s1); l2=strlen(s2); i=0; next[0]=-1; j=-1; while(i<l2){ if(j==-1||s2[i]==s2[j]){ i++; j++; if(s2[i]!=s2[j]) next[i]=j; else next[i]=next[j]; } else j=next[j]; } i=j=0; while(i<l1&&j<l2){ if(j==-1||s1[i]==s2[j]){ i++; j++; } else j=next[j]; } j==l2?printf("%d ",i-j+1):printf("-1 "); } return 0; }
先自己做一下吧。
（四） KMP的应用。
在进行之前咱们讨论一下最小循环节，最小循环周期。
先看一下另一位学长出的题吧。
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2747
循环节
题目描述
输入
输出
示例输入
aaaa abab
示例输出
a ab
这个题的数据是很小的，所以我们完全可以暴力解决。在小白书上有这个几乎一样的题目，暴力的解法。
这个就需要大家自己先做下喽。
#include <stdio.h> #include <stdlib.h> #include <string.h> int main(void) { char s[81]; int i,l,f,j; while(scanf("%s",s)==1){ l=strlen(s); for(i=1;i<=l;i++) if(l%i==0){ for(f=j=i;j<l;j++) if(s[j]!=s[j%i]){ f=0; break; } if(f){ for(j=0;j<i;j++) printf("%c",s[j]); break; } } printf(" "); } return 0; }
既然我们学了KMP当然要多多练习啊，不能浪费啊。
那么我们来分析一下吧。
我们先用KMP求一下next[] ，然后if(len%(len-next[len])==0)那么len/(len-next[len])就是他的最小循环周期，而len/(len/(len-next[len]))==len-next[len] 就是它的最小循环节。
如果len%(len-next[len])==0不成立，就说明这个字符串的最小循环节就是它本身。问题就这样解决了。
#include <stdio.h> #include <string.h> #include <stdlib.h> int getnext(char *s) { int i=0,j=-1,l=strlen(s); int next[81]={-1,}; while(i<l) if(j==-1||s[i]==s[j]) next[++i]=++j; else j=next[j]; if(l%(l-next[l])==0) return l-next[l]; else return l; } int main(void) { char s[81]; int i,j; while(scanf("%s",s)==1){ j=getnext(s); for(i=0;i<j;i++) printf("%c",s[i]); printf(" "); } return 0; }
就这样我们就又学会了一个算法了。兴奋吧，哈哈，做3道题吧。
http://poj.org/problem?id=2406
#include <stdio.h> #include <string.h> #include <stdlib.h> char s[1000005]; int next[1000005]; int getnext() { int i=0,j=-1,l=strlen(s); next[0]=-1; while(i<l) if(j==-1||s[i]==s[j]) next[++i]=++j; else j=next[j]; return l%(l-next[l])==0?l/(l-next[l]):1; } int main(void) { while(scanf("%s",s),s[0]!='.') printf("%d ",getnext()); return 0; }
http://poj.org/problem?id=1961
#include <stdio.h> #include <string.h> #include <stdlib.h> char s[1000005]; int next[1000005]; int l; void getnext() { int i=0,j=-1; l=strlen(s); next[0]=-1; while(i<l) if(j==-1||s[i]==s[j]) { next[++i]=++j; if(i%(i-j)==0&&i/(i-j)>1) printf("%d %d ",i,i/(i-j)); } else j=next[j]; } int main(void) { int i,n,k=0; while(scanf("%d",&n),n){ scanf("%s",s); printf("Test case #%d ",++k); getnext(); printf(" "); } return 0; }
http://hihocoder.com/problemset/problem/1015
1 #include <cstdio> 2 #include <cstring> 3 #include <string.h> 4 #include <queue> 5 #define MAX 27 6 7 using namespace std; 8 9 int next[10003]; 10 char str_one[10003]; 11 char str_two[1000003]; 12 13 void getnext(char *str) 14 { 15 int i, j; 16 int len = strlen(str); 17 18 next[0] = -1; 19 i = 0; 20 j = -1; 21 while(i<len){ 22 if(j == -1 || str[i] == str[j]){ 23 i++; 24 j++; 25 if(str[i] == str[j]) 26 next[i] = next[j]; 27 else 28 next[i] = j; 29 } 30 31 else 32 j = next[j]; 33 } 34 } 35 36 int main() 37 { 38 int len_one; 39 int len_two; 40 int n, i, j, ans; 41 42 scanf("%d",&n); 43 while(n--){ 44 scanf("%s",str_one); 45 getnext(str_one); 46 scanf("%s",str_two); 47 i = 0; 48 j = 0; 49 ans = 0; 50 len_one = strlen(str_one); 51 len_two = strlen(str_two); 52 for(i=0;i<len_two;) 53 { 54 if(j == -1 || str_one[j] == str_two[i]){ 55 j++; 56 i++ 57 } 58 else 59 j = next[j]; 60 if(j == len_one) 61 ans++; 62 } 63 printf("%d ",ans); 64 } 65 return 0; 66 }
大家晚安。