一个类KMP的算法

Nisy

看了一篇KMP算法的文章，对数学公式有点没绕明白，干脆自己琢磨琢磨吧。
Link: http://blog.csdn.net/yaochunnian/article/details/7059486

自己在纸上画了画，逻辑应该是找重复，简单实现了一个自己的逻辑，改天在继续研究。
我的想法是这样的
Test1 :
a a a b
0 0 1 2
Test2 :
a b a b c d
0 0 0 1 2 0
然后根据返回值 j，来判断如何处理。

1. 
   
2. 
   
3. void GetNextval(char const* pstr, int nlen, int* Value)   
   
4. {   
   
5.     int i = 1;
   
6.     int k = 0;
   
7.     int nMax = 0;
   
8.     memset( Value, 0, nlen * sizeof(int));
   
9.     while( i < nlen )   
   
10.     {   
    
11.         // "abaabac";
    
12.         if( *(pstr + i) == *(pstr) )   //循环的if部分   
    
13.         {
    
14.             nMax = k = 0;
    
15.             do
    
16.             {
    
17.                 nMax ++;
    
18.                 Value[i + k + 1] = nMax;
    
19.                 k++;
    
20.             } while ( k < (nlen - i) &&
    
21.                 *(pstr + i + k) == *(pstr + k) );
    
22. 
    
23.             i += k;
    
24.             continue;
    
25.         }
    
26.         i++;
    
27.     }
    
28. }
    
29. 
    
30. void GetNextvalEx(char const* pstr, int nlen, int* Value)   
    
31. {   
    
32.     int i = 1;
    
33.     int k = 0;
    
34.     int nMax = 0;
    
35.     memset( Value, 0, nlen * sizeof(int));
    
36.     while( i < nlen-1 )   
    
37.     {   
    
38.         // "aaaaaab";
    
39.         // "0012345";
    
40.         if( * pstr  == *(pstr + i) )   //循环的if部分   
    
41.         {
    
42.             nMax = k = 0;
    
43.             do
    
44.             {
    
45.                 ++k ;
    
46.                 Value[i + k ] = ++nMax;
    
47.             } while ( i + k  < nlen-1  &&
    
48.                 *(pstr + k) == *(pstr + i + k) );
    
49. 
    
50.             i += k;
    
51.             continue;
    
52.         }
    
53.         i++;
    
54.     }
    
55. }
    
56. 
    
57. int KmpSearch(char const* src, int len1, char const* dest, int len2, int const* Value, int pos)   
    
58. {   
    
59.     int i = pos;   
    
60.     int j = 0;
    
61.     int nIndex = 0;
    
62.     while ( i < len1 && j < len2 )   
    
63.     {   
    
64.         if( src[i] == dest[j] )   
    
65.         {   
    
66.             ++i;   
    
67.             ++j;   
    
68.         }   
    
69.         else   
    
70.         {   
    
71.             j = Value[j];
    
72.             if ( src[i] != dest[j] )
    
73.             {
    
74.                 if ( j != 0 ) // j > 0
    
75.                     j = 0;
    
76.                 ++i;
    
77.             }
    
78.         }   
    
79.     }   
    
80.     if( j == len2 )   
    
81.         nIndex = i-len2;   
    
82.     else   
    
83.         nIndex = -1;   
    
84. 
    
85.     return nIndex;
    
86. }
    
87. 
    
88. int   main()  
    
89. {  
    
90.     std::string src = "abababc";  
    
91.     std::string prn = "abc";  
    
92.     int* nextval = new int[prn.size()];  
    
93.     GetNextval(prn.data(), prn.size(), nextval);
    
94.     int nIndex = KmpSearch(src.data(), src.size(), prn.data(), prn.size(), nextval, 0);
    
95.   // delete ...
    
96. }
    
97. 
    

复制代码

Nisy

直接写的代码 转过来大家看下这样是否更好理解KMP的实现 没有做过测试 若有BUG还望反馈 ~

lucky_789

果断顶！
那篇博文的原作者后来重新写了一篇，比较好理解了，关键是所谓的“前缀、后缀”，前后缀中间的部分为何不用证明不太明白，没学过数论。

lucky_789

经测试，一切正常！

crackvip

我也来占坐学习。。。

small-q

学习啊!

hu251405204

感谢楼主分享！

menglv

居然在这里看到了nisy的kmp源码，测试一下。