• 5、利用求得的next数组各值运用Kmp算法

1. //代码5-1    
2. //int kmp_seach(char const*, int, char const*, int, int const*, int pos)  KMP模式匹配函数    
3. //输入：src, slen主串    
4. //输入：patn, plen模式串    
5. //输入：nextval KMP算法中的next函数值数组    
6. int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)    
7. {    
8.     int i = pos;    
9.     int j = 0;    
10.     while ( i < slen && j < plen )    
11.     {    
12.         if( j == -1 || src[i] == patn[j] )    
13.         {    
14.             ++i;    
15.             ++j;    
16.         }    
17.         else    
18.         {    
19.             j = nextval[j];              
20.             //当匹配失败的时候直接用p[j_next]与s[i]比較，    
21.             //以下阐述怎么求这个值，即匹配失效后下一次匹配的位置    
22.         }    
23.     }    
24.     if( j >= plen )    
25.         return i-plen;    
26.     else    
27.         return -1;    
28. }    

1. //copyright@2011 binghu and july  
2. #include "StdAfx.h"  
3. #include <string>  
4. #include <iostream>  
5. using namespace std;  
6.   
7. //代码4-1    
8. //修正后的求next数组各值的函数代码    
9. void get_nextval(char const* ptrn, int plen, int* nextval)    
10. {    
11.     int i = 0;  //注，此处与下文的代码实现二不同的是，i是从0開始的（代码实现二i从1開始）     
12.     nextval[i] = -1;    
13.     int j = -1;    
14.     while( i < plen-1 )    
15.     {    
16.         if( j == -1 || ptrn[i] == ptrn[j] )   //循环的if部分    
17.         {    
18.             ++i;    
19.             ++j;    
20.             //修正的地方就发生以下这4行    
21.             if( ptrn[i] != ptrn[j] ) //++i，++j之后，再次推断ptrn[i]与ptrn[j]的关系    
22.                 nextval[i] = j;      //之前的错误解法就在于整个推断仅仅有这一句。    
23.             else    
24.                 nextval[i] = nextval[j];    
25.         }    
26.         else                                 //循环的else部分    
27.             j = nextval[j];    
28.     }    
29. }    
30.   
31. void print_progress(char const* src, int src_index, char const* pstr, int pstr_index)  
32. {  
33.     cout<<src_index<<"\t"<<src<<endl;  
34.     cout<<pstr_index<<"\t";  
35.     for( int i = 0; i < src_index-pstr_index; ++i )  
36.         cout<<" ";  
37.     cout<<pstr<<endl;  
38.     cout<<endl;  
39. }  
40.   
41. //代码5-1    
42. //int kmp_seach(char const*, int, char const*, int, int const*, int pos)  KMP模式匹配函数    
43. //输入：src, slen主串    
44. //输入：patn, plen模式串    
45. //输入：nextval KMP算法中的next函数值数组    
46. int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)    
47. {    
48.     int i = pos;    
49.     int j = 0;    
50.     while ( i < slen && j < plen )    
51.     {    
52.         if( j == -1 || src[i] == patn[j] )    
53.         {    
54.             ++i;    
55.             ++j;    
56.         }    
57.         else    
58.         {    
59.             j = nextval[j];              
60.             //当匹配失败的时候直接用p[j_next]与s[i]比較，    
61.             //以下阐述怎么求这个值，即匹配失效后下一次匹配的位置    
62.         }    
63.     }    
64.     if( j >= plen )    
65.         return i-plen;    
66.     else    
67.         return -1;    
68. }    
69.   
70. int   main()  
71. {  
72.     std::string src = "aabcabcebafabcabceabcaefabcacdabcab";  
73.     std::string prn = "abac";  
74.   
75.     int* nextval = new int[prn.size()];  
76.     //int* next = new int[prn.size()];  
77.     get_nextval(prn.data(), prn.size(), nextval);  
78.     //get_next(prn.data(), prn.size(), next);  
79.   
80.     for( int i = 0; i < prn.size(); ++i )  
81.         cout<<nextval[i]<<"\t";  
82.     cout<<endl;  
83.       
84.     cout<<"result sub str: "<<src.substr( kmp_search(src.data(), src.size(), prn.data(), prn.size(), nextval, 0) )<<endl;  
85.     system("pause");  
86.   
87.     delete[] nextval;  
88.     return 0;  
89. }   

  a0a1...aj-1aj

要找到一个k,使它满足

  a0a1...ak-1ak=aj-kaj-k+1...aj-1aj

1. //copyright@ staurman  
2. //updated@2011 July  
3. #include "StdAfx.h"  
4. #include<iostream>  
5. #include<string>  
6. using namespace std;  
7.   
8. //solve to the next array  
9. void compute_overlay(const string& pattern)  
10. {  
11.     const int pattern_length = pattern.size();  
12.     int *overlay_function = new int[pattern_length];  
13.     int index;  
14.     overlay_function[0] = -1;  
15.     for(int i=1;i<pattern_length;++i)      
16.         //注，与上文代码段一不同的是，此处i是从1開始的，所以，下文中运用俩种方法求出来的next数组各值会有所不同  
17.     {  
18.         index = overlay_function[i-1];  
19.         //store previous fail position k to index;  
20.   
21.         while(index>=0 && pattern[i]!=pattern[index+1])  
22.         {  
23.             index = overlay_function[index];  
24.         }  
25.         if(pattern[i]==pattern[index+1])  
26.         {  
27.             overlay_function[i] = index + 1;    
28.         }  
29.         else  
30.         {  
31.             overlay_function[i] = -1;  
32.         }  
33.     }  
34.     for(int i=0;i<pattern_length;++i)  
35.     {  
36.         cout<<overlay_function[i]<<endl;  
37.     }  
38.     delete[] overlay_function;  
39. }  
40.   
41. //abaabcaba  
42. int main()  
43. {  
44.     string pattern = "abaabcaba";  
45.     compute_overlay(pattern);  
46.     system("pause");  
47.     return 0;  
48. }  

1. //copyright@ saturnman  
2. //updated@ 2011 July  
3. #include "stdafx.h"  
4. #include<iostream>  
5. #include<string>  
6. #include <vector>  
7. using namespace std;  
8.   
9. int kmp_find(const string& target,const string& pattern)  
10. {  
11.     const int target_length=target.size();  
12.     const int pattern_length=pattern.size();  
13.     int* overlay_value=http://www.mamicode.com/new int[pattern_length];  
14.     overlay_value[0]=-1;        //remember:next array‘s first number was -1.  
15.     int index=0;  
16.   
17.     //next array  
18.     for (int i=1;i<pattern_length;++i)  
19.         //注，此处的i是从1開始的  
20.     {  
21.         index=overlay_value[i-1];  
22.         while (index>=0 && pattern[index+1]!=pattern[i])  //remember:!=  
23.         {  
24.             index=overlay_value[index];  
25.         }  
26.         if(pattern[index+1] == pattern[i])  
27.         {  
28.             overlay_value[i]=index+1;  
29.         }  
30.         else  
31.         {  
32.             overlay_value[i]=-1;  
33.         }  
34.     }  
35.   
36.     //mach algorithm start  
37.     int pattern_index=0;  
38.     int target_index=0;  
39.     while (pattern_index<pattern_length && target_index<target_length)  
40.     {  
41.         if (target[target_index] == pattern[pattern_index])  
42.         {  
43.             ++target_index;  
44.             ++pattern_index;  
45.         }   
46.         else if(pattern_index==0)  
47.         {  
48.             ++target_index;  
49.         }  
50.         else  
51.         {  
52.             pattern_index=overlay_value[pattern_index-1]+1;  
53.         }  
54.     }  
55.     if (pattern_index==pattern_length)  
56.     {  
57.         return target_index-pattern_index;  
58.     }   
59.     else  
60.     {  
61.         return -1;  
62.     }  
63.     delete [] overlay_value;  
64. }  
65.   
66. int main()  
67. {  
68.     string sourc="ababc";  
69.     string pattern="abc";  
70.     cout<<kmp_find(sourc,pattern)<<endl;  
71.     system("pause");  
72.     return 0;  
73. }  

1. //copyright@ staurman  
2. //updated@2011 July  
3. #include "StdAfx.h"  
4. #include<iostream>  
5. #include<string>  
6. using namespace std;  
7.   
8. //solve to the next array  
9. void compute_overlay(const string& pattern)  
10. {  
11.     const int pattern_length = pattern.size();  
12.     int *overlay_function = new int[pattern_length];  
13.     int index;  
14.     overlay_function[0] = -1;  
15.     for(int i=1;i<pattern_length;++i)  
16.     {  
17.         index = overlay_function[i-1];  
18.         //store previous fail position k to index;  
19.   
20.         while(index>=0 && pattern[i]!=pattern[index+1])  
21.         {  
22.             index = overlay_function[index];  
23.         }  
24.         if(pattern[i]==pattern[index+1])  
25.         {  
26.             overlay_function[i] = index + 1;    
27.         }  
28.         else  
29.         {  
30.             overlay_function[i] = -1;  
31.         }  
32.     }  
33.     for(int i=0;i<pattern_length;++i)  
34.     {  
35.         cout<<overlay_function[i]<<endl;  
36.     }  
37.     delete[] overlay_function;  
38. }  
39.   
40. //abaabcaba  
41. int main()  
42. {  
43.     string pattern = "abaabcaba";  
44.     compute_overlay(pattern);  
45.     system("pause");  
46.     return 0;  
47. }  

1. //copyright@ saturnman  
2. //updated@ 2011 July  
3. #include "stdafx.h"  
4. #include<iostream>  
5. #include<string>  
6. #include <vector>  
7. using namespace std;  
8.   
9. int kmp_find(const string& target,const string& pattern)  
10. {  
11.     const int target_length=target.size();  
12.     const int pattern_length=pattern.size();  
13.     int* overlay_value=http://www.mamicode.com/new int[pattern_length];  
14.     overlay_value[0]=-1;        //remember:next array‘s first number was -1.  
15.     int index=0;  
16.   
17.     //next array  
18.     for (int i=1;i<pattern_length;++i)  
19.         //注，此处的i是从1開始的  
20.     {  
21.         index=overlay_value[i-1];  
22.         while (index>=0 && pattern[index+1]!=pattern[i])    
23.         {  
24.             index=overlay_value[index];  
25.         }  
26.         if(pattern[index+1] == pattern[i])  
27.         {  
28.             overlay_value[i]=index+1;  
29.         }  
30.         else  
31.         {  
32.             overlay_value[i]=-1;  
33.         }  
34.     }  
35.   
36.     //mach algorithm start  
37.     int pattern_index=0;  
38.     int target_index=0;  
39.     while (pattern_index<pattern_length && target_index<target_length)  
40.     {  
41.         if (target[target_index] == pattern[pattern_index])  
42.         {  
43.             ++target_index;  
44.             ++pattern_index;  
45.         }   
46.         else if(pattern_index==0)  
47.         {  
48.             ++target_index;  
49.         }  
50.         else  
51.         {  
52.             pattern_index=overlay_value[pattern_index-1]+1;  
53.         }  
54.     }  
55.     if (pattern_index==pattern_length)  
56.     {  
57.         return target_index-pattern_index;  
58.     }   
59.     else  
60.     {  
61.         return -1;  
62.     }  
63.     delete [] overlay_value;  
64. }  
65.   
66. int main()  
67. {  
68.     string sourc="ababc";  
69.     string pattern="abc";  
70.     cout<<kmp_find(sourc,pattern)<<endl;  
71.     system("pause");  
72.     return 0;  
73. }  

1. 语言->数据结构->算法：语言是基础，够啃一辈子，主要的常见的数据结构得了如指掌，最后才是算法。除了算法之外，有很多其它更重要且更值得学习的东西（最重要的是，学习怎样编程）。切勿盲目跟风，找准自己的兴趣点，和领域才是关键。这跟选择职位、与领域并持久做下去，比选择公司更重要一样。选择学什么东西不重要，重要的是你的兴趣。
2. 修订这篇文章之时，个人接触KMP都有一年了，学算法也刚好快一年。想想阿，我弄一个KMP，弄了近一年了，到今天才算是真正彻底理解其思想，可想而知，当初创造这个算法的k、m、p三人是何等不易。我想，有不少读者是由于我的出现而想学算法的，但不可急功近利，切勿妄想算法速成。早已说过，学算法先修心。