学步园

对kmp算法的理解可以参考Introduction to Algorithm 3rd Edition Chapter 32.4

如果没有这本书的同学，可以看看下面

KMP-MATCHER(T, P) 

 1 n ← length[T] 

 2 m ← length[P] 

 3 π ← COMPUTE-PREFIX-FUNCTION(P) 

 4 q ← 0                          ▹Number of characters matched. 

 5 for i ← 1 to n                 ▹Scan the text from left to right. 

 6      do while q > 0 and P[q + 1] ≠ T[i] 

 7             do q ← π[q]    ▹Next character does not match. 

 8         if P[q + 1] = T[i] 

 9            then q ← q + 1      ▹Next character matches. 

10         if q = m                    ▹Is all of P matched? 

11            then print "Pattern occurs with shift" i - m 

12                 q ← π[q]    ▹Look for the next match. 

COMPUTE-PREFIX-FUNCTION(P) 

 1 m ← length[P] 

 2 π[1] ← 0 

 3 k ← 0 

 4 for q ← 2 to m 

 5      do while k > 0 and P[k + 1] ≠ P[q] 

 6             do k ← π[k] 

 7         if P[k + 1] = P[q] 

 8            then k ← k + 1 

 9         π[q] ← k 

10 return π

很多网页上面都有对该算法的解释和说明

<1> http://blog.csdn.net/liuben/archive/2009/08/04/4409505.aspx

<2> http://www.ics.uci.edu/~eppstein/161/960227.html

<3> http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

<4> http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm

ps2: 下面是用c语言按照网页索引<3>的一个小实现

/* checkout the page below</p> <p>http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm</p> <p>*/ </p> <p>#include <stdlib.h><br /> #include <stdio.h><br /> #include <string.h><br /> #include <assert.h><br /> void kmp_table(const char* w, int **t)<br /> {<br /> int pos = 2;<br /> int cnd = 0;<br /> assert(NULL != w && NULL != t);<br /> *t = (int *)malloc(strlen(w) + 1);<br /> if(NULL != *t)<br /> memset(*t, 0x00, strlen(w) + 1);<br /> else<br /> exit(EXIT_FAILURE);<br /> **t = -1;<br /> *(*t + 1) = 0;<br /> while( pos < strlen(w)) {<br /> if(*(w + pos - 1) == *(w + cnd)){<br /> *(*t + pos) = cnd + 1;<br /> pos++;<br /> cnd++;<br /> }<br /> else if(cnd > 0) {<br /> cnd = *(*t + cnd);<br /> }<br /> else {<br /> *(*t + pos) = 0;<br /> pos++;<br /> }<br /> }<br /> #ifdef DEBUG<br /> {<br /> int i = -1;<br /> while(++i < strlen(w)) {<br /> printf("table[%d] is %d/n", i, *(*t + i));<br /> }<br /> }<br /> #endif<br /> }<br /> void kmp_freetable(int *t)<br /> {<br /> if(NULL != t )<br /> free((void*)t);<br /> }<br /> int kmp_search(const char *s, const char* w)<br /> {<br /> int m = 0, i = 0;<br /> int *table;<br /> kmp_table(w, &table);<br /> while((m + i) < strlen(s)) {<br /> if(*(w + i) == *(s + m + i)) {<br /> i++;<br /> if(i == strlen(w)) {<br /> return m;<br /> }<br /> }<br /> else {<br /> m = m + i - table[i];<br /> if(i > 0)<br /> i = table[i];<br /> }<br /> }</p> <p> kmp_freetable(table);<br /> /* since we got here, no match found */<br /> return strlen(s);<br /> }</p> <p>int main ( int argc, char *argv[] )<br /> {<br /> char* s = "abc abcdab abcdabcdabde";<br /> char* t = "abcdabd";<br /> printf("result %d/n", kmp_search(s, t));</p> <p> return EXIT_SUCCESS;<br /> }