首页 > 代码库 > KMP——华丽丽的字符串
KMP——华丽丽的字符串
今天呢 ，再次在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("\n"); for(i=0;i<=l;i++) printf("%4d",next[i]); printf("\n");}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]=‘\0‘的前一位是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\n"); else printf("No\n");}
当你与女神能匹配就输出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\n",i-j+1):printf("-1\n"); } return 0;}
先自己做一下吧。
（四） KMP的应用。
在进行之前咱们讨论一下最小循环节，最小循环周期。
先看一下另一位学长出的题吧。
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2747
循环节
题目描述
输入
输出
示例输入
aaaaabab
示例输出
aab
这个题的数据是很小的，所以我们完全可以暴力解决。在小白书上有这个几乎一样的题目，暴力的解法。
这个就需要大家自己先做下喽。
#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("\n"); } 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("\n"); } return 0;}
就这样我们就又学会了一个算法了。兴奋吧，哈哈，做2道题吧。
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\n",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\n",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\n",++k); getnext(); printf("\n"); } return 0;}
好了 ，就将这些吧，很多地方讲的不好的请多多原谅。世界杯直播都没看，哎，但是我买的德国：葡萄牙的主场胜 现在比分3:0。哈哈。
大家晚安。