C語言中實現(xiàn)KMP算法的實例講解
一般的算法為什么這么低效呢?那是因為主串指針回溯情況過多:
主串指針如果不回溯的話,速度就會加快,那我們就會想:
如何讓主串指針不回溯?
KMP算法就是解決了這個問題,所以速度變得更快速了。
它是這樣子的:
用一個數(shù)組:next[] 求得失配時的位置,然后保存下來。
要說清楚KMP算法,可以從樸素的模式匹配算法說起。
樸素的模式匹配算法比較容易理解,其實現(xiàn)如下
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; } }
可見,在樸素的模式匹配算法中,當(dāng)模式中的p[j]與主串中的s[i]不匹配時,需要把主串的指針回溯到i-j+1的地方從新用s[i-j+1]跟p[0]進(jìn)行匹配比較。KMP算法的想法是,能不能不回溯主串的指針呢?這種想法基于如下事實的:p[j]!=s[i]前,p[0]~p[j-1]跟s[i-j]~s[i-1]是匹配的(這里j>0,也就是說在不匹配前已經(jīng)有匹配的字符了。否則如果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是滿足這個關(guān)系的最大值),則可以知道s[i-k]~s[j-1]跟[0]~p[k-1]是匹配的,那么,s[i]只需要跟p[k]進(jìn)行比較就行了。而這個k是跟主串無關(guān)的,只需要分析模式串就可以求出來(這就是普通的教材中next[j]=k這個假設(shè)的由來,普通教材中總喜歡假設(shè)這個k值已經(jīng)有了,如果你邏輯思維強(qiáng)還沒有什么,不然或多或少會把你卡在這的)。亦即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]為結(jié)尾的子串跟模式p都是失配的?;谏厦鎝[0]~p[j-1]=s[i-j]~s[i-1]的事實,可以斷定s[i-j]~s[i-1]中所有以s[i-1]結(jié)尾的子串跟模式p都是失配,這說明把主串的指針回溯到i-j+1~i-1都是沒有必要的,既然沒有必要回溯,而s[i]!=p[j],則s[i只能跟p[0]進(jìn)行比較匹配了。亦即next[j]=0。
特殊情況下,j=0,即s[i]!=p[0],這時不用再用s[i]來跟p中的其它字符比較了,變成用s[i+1]跟p[0]進(jìn)行比較。為了統(tǒng)一,可以讓next[0]=-1。在下一輪的比較中,判斷到j(luò)=-1的情況時,讓i=i+1,j=j+1,自然就形成s[i+1]跟p[0]比較的效果了。
KMP算法實現(xiàn)示例
具體請看如下程序:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 101 void 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 <= la ) { if(A[i] == a[j] || j == 0 ) { i ++ ; j ++ ; } else j = next[j] ; } if ( j> 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 ; }
您可能感興趣的文章
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用函數(shù)刪除字符
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)式函數(shù)庫
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言中對數(shù)函數(shù)的表達(dá)式 c語言中對數(shù)怎么表達(dá)
- 04-02c語言用函數(shù)寫分段 用c語言表示分段函數(shù)
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排序法函數(shù)
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段函數(shù)
- 04-02C語言中怎么打出三角函數(shù) c語言中怎么打出三角函數(shù)的值
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求階乘


閱讀排行
本欄相關(guān)
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對數(shù)函數(shù)的表達(dá)式 c語言中對
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機(jī)閱讀
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 01-11ajax實現(xiàn)頁面的局部加載
- 08-05DEDE織夢data目錄下的sessions文件夾有什
- 01-10delphi制作wav文件的方法
- 01-10SublimeText編譯C開發(fā)環(huán)境設(shè)置
- 01-10C#中split用法實例總結(jié)
- 08-05dedecms(織夢)副欄目數(shù)量限制代碼修改
- 01-10使用C語言求解撲克牌的順子及n個骰子
- 04-02jquery與jsp,用jquery
- 08-05織夢dedecms什么時候用欄目交叉功能?