// kmp.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" char pattern[] = "abaabaabbcdf"; char text[] = "abaabaabbcdfkashdfirabcabcedbyuvabcabddcdscgyuvwb,mbkabcabcedabaabaabbcdfdcdsjciuzxqwmd,sanfixcvjwqkfniozxyciuwqfksgiuytsw"; int next[sizeof(pattern)-1]; void getNext(char* p){ int len = strlen(p); int count = 0; next[0] = 0; for( int num = 1; num < len; num++ ){ //注意下面这个的理解 //若b(s+1) while( count>0 && p[num]!=p[count] ) count = next[count-1]; if( p[num]==p[count] ) { count++; next[num] = count; } else { next[num] = 0; } } } int KMP(char* text_,char* pattern,int* next){ char* text = text_; char* p = pattern; int count = 0; while( NULL!=*text ){ while( pattern==p && *text!=*p ) text++; while( *text==*p ){ text++; p++; count++; } if( count!= 0){ if( strlen(pattern)==count ) //返回在字符串中匹配到的起始位置 return text - count - text_ + 1; else{ p = pattern + next[count-1]; count = 0 ; } } } return -1; } //按照书上的思想进行的算法改进 int KMP_(const char* text,const char* pattern,const int* next){ int count = 0; for( int i=0;i<strlen(text);i++ ){ while( count>0 && *(text+i)!=*( pattern+count ) ) count = next[count-1]; if( *(text+i)==*( pattern+count ) ){ count++; } if( strlen(pattern)==count ) //返回在字符串中匹配到的起始位置(由0开始) return i-count+1; } return -1; } int _tmain(int argc, _TCHAR* argv[]) { getNext(pattern); //for(int i=0;i<sizeof(pattern)-1;i++) // printf("%d ",next[i]); printf("%s/n",text); printf("%d",KMP_(text,pattern,next)); getchar(); return 0; }
今天又把KMP算法看了一边，虽然以前读过相关的代码，并且知道它里面的一些基本思想概念：如状态机、前缀串等，但一直没有认真体会，今天不同之处在于自己把相应的算法写出来，于是九牛二虎，写完以上代码。
在构造状态转移函数时，即这里的NEXT[]数组，最重要的一步是：
while( count>0 && p[num]!=p[count] ) count = next[count-1];
看上去两行代码，其实背后包含许多，如count本质是记录匹配的最长前缀长度，而next[count-1],p[count]再加一个while循环，实则是寻找一个更短的前缀。
在进行具体的字符串查找函数中，我自己写了int KMP(char* text_,char* pattern,int* next);比较好理解匹配的思想。
不过看完书上的代码后，惊叹与它的简洁，于是重写了int KMP_(const char* text,const char* pattern,const int* next);
代码精炼多了，不过理解起来确实也要费点时间。
有空把代码在重写几遍，加强理解。
