1 //s是模式字符串，t是匹配字符串（可以看我上一篇文章中的敘述）
 2 int KMP(const char * s , const char * t)
 3 {
 4     int slen = strlen(s) , tlen = strlen(t);
 5     int i = 0 , j = 0;
 6     int *next = ( int * )malloc( sizeof( int ) * slen );

 7     GetNextVal( s , next); //生成部分匹配值的函數(shù)
 8     while( i < slen && j < tlen )
 9     {
10         if(s[i] == t[j])
11         {
12             i++;
13             j++;
14         }
15         else
16             if(i == 0)
17             {
18                  j = j + 1;//如果第一個(gè)字符都不匹配，就直接移一位
19             }
20             else
21             {
22   //按照上一篇文章中寫的，移動(dòng)步數(shù) = 已匹配字符 - 匹配值
23   //算式應(yīng)該是：j = ( j - i )+ ( i - next[i-1] ) ;(j - i )為首字符所在的位置
24   //化簡(jiǎn)后為：j = j - next[i-1]; 再將匹配字符串的索引歸0; i = 0;
25   //但我們發(fā)現(xiàn)，對(duì)于之前已經(jīng)匹配的字符我們又重新比較了一次，
26   //所以進(jìn)行修正，j的值不變，移動(dòng)匹配字符串，即 i = next[i-1]; 
27 
28                  i = next[i-1];            
29             }
30     }
       free( next );
31     if( i == slen )               //說(shuō)明匹配成功
32         return j - slen;        //返回目標(biāo)字符串中匹配字符串的位置
33     else
34         return -1;                //表示匹配失敗
35 }

 1 void * GetNextVal( const char *s , int *temp )
 2 {
 3     int i = 0 , j = 0;
 4
 5     temp[0] = 0;
 6     
 7     while( i < len)
 8     { 
 9         i++;
10         if ( s[i] == s[j] )
11         {
12             j++;
13             temp[i] = j;
14         }
15         else
16         {
17              j = 0;
18              if ( s[i] == s[j] )
19              {
20                  j++;
21                  temp[i] == j;
22              }
23              else
24              {
25                  temp[i] == j;
26              }
27         }
28     }    
29 }