C語言中實現KMP算法實例

一般的算法為什麼這麼低效呢？那是因為主串指針回溯情況過多:

主串指針如果不回溯的話，速度就會加快，那我們就會想：

如何讓主串指針不回溯？

KMP算法就是解決了這個問題，所以速度變得更快速了。

它是這樣子的：

用一個數組：next[] 求得失配時的位置，然後保存下來。

要説清楚KMP算法，可以從樸素的模式匹配算法説起。

樸素的模式匹配算法比較容易理解，其實現如下

int Index(char s[], char p[], int pos) { int i, j, slen, plen; i = pos; j = 0; slen = strlen(s); plen = strlen(p); while((i < slen) && (j < plen)) { if((s[i] == p[j])) { i++; j++; } else { i = i-j+1; j = 0; } } if(j >= plen) { return (i-plen); } else { return -1; } }

可見，在樸素的模式匹配算法中，當模式中的p[j]與主串中的s[i]不匹配時，需要把主串的指針回溯到i-j+1的地方從新用s[i-j+1]跟p[0]進行匹配比較。KMP算法的想法是，能不能不回溯主串的.指針呢？這種想法基於如下事實的：p[j]!=s[i]前，p[0]~p[j-1]跟s[i-j]~s[i-1]是匹配的（這裏j>0，也就是説在不匹配前已經有匹配的字符了。否則如果j=0,則主串指針肯定不用回溯，直接向前變成i+1再跟p[0]比較就是了）

p[j]!=s[i]前，p[0]~p[j-1]跟s[i-j]~s[i-1]是匹配的，這説明了什麼呢？這説明可以通過分析模式的p[0]~p[j-1]來分析s[i-j]~s[i-1]。如果模式中存在p[0]~p[k-1]=p[j-k]~p[j-1](共k個匹配的字符,且k是滿足這個關係的最大值）,則可以知道s[i-k]~s[j-1]跟[0]~p[k-1]是匹配的，那麼，s[i]只需要跟p[k]進行比較就行了。而這個k是跟主串無關的，只需要分析模式串就可以求出來（這就是普通的教材中next[j]=k這個假設的由來,普通教材中總喜歡假設這個k值已經有了，如果你邏輯思維強還沒有什麼，不然或多或少會把你卡在這的）。亦即next[j]=k。

如果上述的p[0]~p[k-1]=p[j-k]~p[j-1]串不存在會怎麼樣呢？這説明p[j]前的串中不存在p[0]...=...p[j-1]的情況，就連p[0]也不等於p[j-1],也就是説p[0]~p[j-1]中所有以p[j-1]為結尾的子串跟模式p都是失配的。基於上面p[0]~p[j-1]=s[i-j]~s[i-1]的事實，可以斷定s[i-j]~s[i-1]中所有以s[i-1]結尾的子串跟模式p都是失配，這説明把主串的指針回溯到i-j+1～i-1都是沒有必要的，既然沒有必要回溯，而s[i]!=p[j]，則s[i只能跟p[0]進行比較匹配了。亦即next[j]=0。

特殊情況下，j=0，即s[i]!=p[0]，這時不用再用s[i]來跟p中的其它字符比較了，變成用s[i+1]跟p[0]進行比較。為了統一，可以讓next[0]=-1。在下一輪的比較中，判斷到j=-1的情況時，讓i=i+1,j=j+1,自然就形成s[i+1]跟p[0]比較的效果了。

KMP算法實現示例

具體請看如下程序：

#include#include#include#define MAX 101void get_next( int *next,char *a,int la) /*求NEXT[]的值*/{ int i=1,j=0 ; next[1] = 0 ; while ( i <= la) /*核心部分*/ { if( a[i] == a[j] || j == 0 ) { j ++ ; i ++ ; if( a[i] == a[j]) next[i] = next[j]; else next[i] = j ; } else j = next[j] ; }}int str_kmp( int *next, char *A ,char *a, int lA,int la)/* EASY*/{ int i,j,k ; i = 1 ; j = 1 ; while ( i<=lA && j <= 0="" la="" j="" i="" else="" if=""> la) return i-j+1 ; else return -1 ;}int main(void){ int n,k; int next[MAX]={0} ; int lA=0,la =0 ; char A[MAX],a[MAX] ; scanf("%s %s",A,a) ; lA = strlen(A); la = strlen(a); for(k=la-1; k>= 0 ;k --) a[k+1] = a[k] ; for(k=lA-1; k>= 0 ;k --) A[k+1] = A[k] ; get_next(next,a,la) ; k = str_kmp(next,A,a,lA,la); if ( -1 == k) printf("Not Soulation!!! "); else printf("%d ",k) ; system("pause"); return 0 ;}