資源描述：
《kmp模式匹配算法探討》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。
1、從本學(xué)科出發(fā)，應(yīng)著重選對(duì)國(guó)民經(jīng)濟(jì)具有一定實(shí)用價(jià)值和理論意義的課題。課題具有先進(jìn)性，便于研究生提出新見(jiàn)解，特別是博士生必須有創(chuàng)新性的成果KMP模式匹配算法探討摘要介紹了ＫＭＰ算法并與樸素查找算法進(jìn)行了比較，提出了前綴函數(shù)的概念，并利用改進(jìn)的前綴函數(shù)改進(jìn)KMP算法，最后結(jié)合ＫＭＰ的改進(jìn)算法給出了多次匹配的算法。關(guān)鍵詞串匹配，前綴函數(shù)，KMP算法在計(jì)算機(jī)科學(xué)領(lǐng)域，串的模式匹配算法一直都是研究焦點(diǎn)之一。在拼寫(xiě)檢查、語(yǔ)言翻譯、數(shù)據(jù)壓縮、搜索引擎、網(wǎng)絡(luò)入侵檢測(cè)、計(jì)算機(jī)病毒特征碼匹配以及DNA序列匹配等應(yīng)用中，都需要進(jìn)行串匹配。串匹配就是在主串中查找模式串的一個(gè)或所有出現(xiàn)。在本文中主串表示
2、為S=s1s2s3…sn，模式串表示為T=t1t2…tm。串匹配從方式上可分為精確匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法、BM算法及一些改進(jìn)算法。本文主要在精確匹配方面對(duì)KMP算法進(jìn)行了討論并對(duì)它做一些改進(jìn)以及利用改進(jìn)的KMP來(lái)實(shí)現(xiàn)多次模式匹配。課題份量和難易程度要恰當(dāng)，博士生能在二年內(nèi)作出結(jié)果，碩士生能在一年內(nèi)作出結(jié)果，特別是對(duì)實(shí)驗(yàn)條件等要有恰當(dāng)?shù)墓烙?jì)。從本學(xué)科出發(fā)，應(yīng)著重選對(duì)國(guó)民經(jīng)濟(jì)具有一定實(shí)用價(jià)值和理論意義的課題。課題具有先進(jìn)性，便于研究生提出新見(jiàn)解，特別是博士生必須有創(chuàng)新性的成果最簡(jiǎn)單的樸素串匹配算法(BF算法)是從主串的第一個(gè)字符和模式串的
3、第一個(gè)字符進(jìn)行比較，若相等則繼續(xù)逐個(gè)比較后續(xù)字符，否則從主串的第二個(gè)字符起再重新和模式串的第一個(gè)字符進(jìn)行比較。依次類推，直至模式串和主串中的一個(gè)子串相等，此時(shí)稱為匹配成功，否則稱為匹配失敗。樸素模式匹配算法匹配失敗重新比較時(shí)只能向前移一個(gè)字符，若主串中存在和模式串只有部分匹配的多個(gè)子串，匹配指針將多次回溯，而回溯次數(shù)越多算法的效率越低，它的時(shí)間復(fù)雜度一般情況下為O((n-m+1)m)，最壞的情況下為O(m*n)，最好的情況下為O(m+n)。KMP模式匹配算法正是針對(duì)上述算法的不足做了實(shí)質(zhì)性的改進(jìn)。其基本思想是：當(dāng)一趟匹配過(guò)程中出現(xiàn)失配時(shí)，不需回溯主串，而是充分利用已經(jīng)得到的部
4、分匹配所隱含的若干個(gè)字符，過(guò)濾掉那些多余的比較，將模式串向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較，從而提高模式匹配的效率，該算法的時(shí)間復(fù)雜度為O(m+n)。那么如何確定哪些是多余的比較？在KMP算法中通過(guò)引入前綴函數(shù)f(x)來(lái)確定每次匹配不需要比較的字符，保證了匹配始終向前進(jìn)行，無(wú)須回溯。假設(shè)主串為s1s2，sn.，模式串為t1t2，tm.，其中m≦n，從si+1開(kāi)始的子串遇到一個(gè)不完全的匹配，使得：()如果我們能確定一個(gè)最小的整數(shù)，使得：()其中，所以確定i'等價(jià)于確定k，這里的k值就是我們要求的前綴函數(shù)f(x)。由式和中K值與主串s無(wú)關(guān)，只與給定的模式串t中與主串匹
5、配的q有關(guān)，即k=f(q)，f(q)=max{i
6、0iq且t[1..i]是t[1..q]的后綴}()確定KMP前綴函數(shù)的算法如下：#defineMAXSIZE100Typedefunsignedcharstring[MAXSIZE+1];//0號(hào)單元用來(lái)存放串的長(zhǎng)度voidf(sstringt,int*array){m=t[0];//m為當(dāng)前模式串的長(zhǎng)度array=(int*)malloc((m+1)*sizeof(int));//0號(hào)元不用課題份量和難易程度要恰當(dāng)，博士生能在二年內(nèi)作出結(jié)果，碩士生能在一年內(nèi)作出結(jié)果，特別是對(duì)實(shí)驗(yàn)條件等要有恰當(dāng)?shù)墓烙?jì)。從本學(xué)科出發(fā)，應(yīng)著重選對(duì)
7、國(guó)民經(jīng)濟(jì)具有一定實(shí)用價(jià)值和理論意義的課題。課題具有先進(jìn)性，便于研究生提出新見(jiàn)解，特別是博士生必須有創(chuàng)新性的成果array[1]=0;k=0;for(q=2;q{while(k>0&&t[k+1]!=t[q])k=array[k];if(t[k+1]==t[q])k=k+1;array[q]=k;}}關(guān)于KMP算法的前綴函數(shù)f(x)的示例見(jiàn)表1。表1模式串a(chǎn)baabcacITiabaabcacf(i)當(dāng)模式串中有i個(gè)字符串匹配成功，第i+1個(gè)字符不匹配時(shí)，則從i-f(i)個(gè)字符重新開(kāi)始比較，這樣不僅無(wú)須回溯，而且一次可以向前滑動(dòng)i-f(i)個(gè)字符，大大提高了模式匹配的效率。下面
8、給出樸素匹配算法和KMP匹配算法的比較，見(jiàn)表2。表樸素匹配算法和KMP匹配算法比較表樸素算法KMP算法時(shí)間復(fù)雜度O((n-m+1)m)O(m+n)向前移動(dòng)字符個(gè)數(shù)1q-f(q)回溯次數(shù)q-1無(wú)其中：n為主串長(zhǎng)度，m為模式串長(zhǎng)度，q為匹配成功的字符個(gè)數(shù)。2KMP算法的改進(jìn)在KMP算法的實(shí)際應(yīng)用中，發(fā)現(xiàn)該算法也存在著不足，結(jié)合下面的表一來(lái)論述KMP模式匹配算法的改進(jìn)。假設(shè)模式串前4個(gè)字符與主串的第i+1..i+4匹配成功，第5個(gè)字符匹配失敗，此時(shí)前綴函數(shù)f(4)=1，下一次匹配將從第i+4開(kāi)始，并直接將模式
