模式匹配算法的原理及應用

1、模式匹配算法的原理及應用,,引言,在計算機科學領(lǐng)域，串的模式匹配（算法一直都是研究焦點之一。在拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、搜索引擎、網(wǎng)絡入侵檢測、計算機病毒特征碼匹配以及DNA序列匹配等應用中，都需要進行串匹配。串匹配就是在主串中查找模式串的一個或所有出現(xiàn)。,1.樸素的模式匹配算法,樸素的模式匹配算法的核心思想是:一旦某個字符匹配失敗,從頭開 始(即從本次匹配起點后一個字符開始 ）.主串 （S）a b a b c a b

2、c a c b a b 子串 （T）a b c a c （子串又被稱為模式串）紅色表示當前這趟比較指針所在位置，蘭色表示當前這趟比較中匹配的部分 第一趟（詳細過程）a b a b c a b c a c b a b a b c a ca b a b c a b c a c b a b a b c a ca b a b c a b c a c b a b a b c a c遇到不匹配的地方時指針

3、回朔，每次移動一位,1.樸素的模式匹配算法,第二趟 a b a b c a b c a c b a b a b c a c第三趟 a b a b c a b c a c b a b a b c a c第四趟 a b a b c a b c a c b a b

4、 a b c a c第五趟 a b a b c a b c a c b a b a b c a c第六趟 a b a b c a b c a c b a b a b c a c _

5、完成匹配，跳出,假如串的長度為m,子串的長度為n的話，那么這個算法在最壞的情況下的時間復雜度為O(m*n) ,結(jié)論：樸素的模式匹配效率低，機械化地去重復匹配了已經(jīng)比較過的內(nèi)容。問題:有沒有辦法降低它的時間復雜度呢？ 當然有！ ^_^,2.模式匹配算法的改進—KMP算法,由D.E.Knuth, J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)的改進模式匹配算法，簡稱為KMP算法。 其基本思想是

6、：每當匹配過程中出現(xiàn)字符串比較不等時，不需回溯主串，而是充分利用已經(jīng)得到的“部分匹配”結(jié)果，過濾掉那些多余的比較，將模式串向右“滑動”盡可能遠的一段距離后，繼續(xù)進行比較，從而提高模式匹配的效率。KMP算法核心之處在于：主串指針不用回溯，直接前進！不匹配時子串指針回退。該算法的時間復雜度為O (m+n)。,2.模式匹配算法的改進—KMP算法,2.1Next的函數(shù)的引出: 分析：要想改進模式匹配的算法,必須減少無效比較,讓起點自

7、動移到當前認為的最理想的位置,而不是僅僅只移一位.但是,計算機怎么知道要移幾位呢? 解決方法：設置一個next數(shù)組 那么next的函數(shù)到底是什么呢? next[j]表示當模式串中第j個字符與主串某個字符比較失敗后,起點應該向后移幾位. (j=next（j）),2.模式匹配算法的改進—KMP算法,2.2Next的函數(shù)的定義和計算: 求next數(shù)組本質(zhì)上就是一個模式串T和自己進行匹配的過程

8、。,,,,2.模式匹配算法的改進—KMP算法,void getnext (SString t, int next[]){ int j=1,k=0; next[1]=0; while (j <= t.len) { if (k==0 || t.date [j] == t.date [k]) { j++; k++; next [j]=k;

9、 } else k=next [k]; // j不變（不回溯）,k回溯 }} 時間復雜度為O(n),,2.模式匹配算法的改進—KMP算法,2.3主程序int kmpindex ( SString s, SString t ){ int next [ Maxlen ],i=1,

10、j=1,v; getnext ( t,next ); while (i t.len ) v = i - t.len; // 若找到,返回主串的匹配首址 else v=-1; //若沒找,返回-1 reture v; } 時間復雜度位O(m

11、),2.模式匹配算法的改進—KMP算法,主串S a b a b c a b c a c b a b 子串T a b c a c next（j） 0 1 1 1 2,按照KMP算法，我們再來看看前面我們舉的例子。第一趟a b a b c a b c a c b a b a b c a c第二趟a b a b c a b c a c b a b a b c

12、a c第三趟a b a b c a b c a c b a b a b c a c _完成匹配，跳出,修正next [j],我們看下面的序列S: aabaabbaaaaaabT: aaaabnext(j) 01234 這樣求出來的next串還不一定最優(yōu)必須找到更優(yōu)的next數(shù)組。 T串中的‘a(chǎn)’和S串中的‘b’失配，而‘a(chǎn)

13、’的next值指的還是‘a(chǎn)’，那同樣的比較還是會失配，而這樣的比較是多余的，如果事先設定，當T[i]==T[j]，那next[i]就設為next[j]，在求next值的時候就已經(jīng)比較了，這樣就可以去掉這樣的多余的比較。于是稍加改進得到： T: aaaab next(j) 01234nextval(j) 00004,源代碼：求修正的nextval[j],void getnextval

14、(SString t, int nextval[]){ int j=1,k=0; nextval[1]=0; while (j<=t.len) { if (k==0|| t.date[j]==t.date[k]) { j++;k++; if (t.date[j]!=t.date[k]) nextval[j]=k

15、; else nextval[j]=nextval[k]; //消去多余的比較 } else k=nextval[k]; }},KMP算法的C#源代碼,# include # include //kmp algorithm//getNext -------求模式串t[ ]的next[ ]---即滑動位置數(shù)組int * getNext( int t[ ], in

16、t nextVal[ ] ){int i = 1，j = 0;nextVal[1] = 0;while( i < t[0] ){if ( j == 0 || t[i] == t[j] ){i++;j++;if ( t[i] != t[j] ) nextVal[i] = j;else nextVal[i] = nextVal[j];}else j = nextVal

17、[j];}return nextVal;},KMP算法的C#源代碼,//indexKMP ------kmp主程序int indexKMP(char s[ ], int t[ ], int next[ ], int pos ){int i = pos;//主串指針int j = 1;//模式串指針while( i t[0] )return i-t[0];else return -1;