字符串匹配算法的研究-本科論文

PAGEPAGE16 1字符串匹配算法的研究及其程序?qū)崿F(xiàn)計(jì)算機(jī)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)2007級指導(dǎo)教師：滕云摘要：在字符串匹配算法之中，最古老和最著名的是由D.E.Knuth,J.h.Morris,V.R.Pratt在1997年共同提出的KMP算法。直至今日，人們對字符串匹配問題還在進(jìn)行著大量的研究，以尋求更簡單，或者平均時間復(fù)雜度更優(yōu)的算法;學(xué)者們在不同的研究方向上，設(shè)計(jì)出了很多有效的匹配算法。在現(xiàn)實(shí)生活中，串匹配技術(shù)的應(yīng)用十分廣泛，其主要領(lǐng)域包括：入侵檢測，病毒檢測，信息檢索，信息過濾，計(jì)算生物學(xué)，金融檢測等等。在許多應(yīng)用系統(tǒng)中，串匹配所占的時間比重相當(dāng)大，因此，串匹配算法的速度很大程度上影響著整個系統(tǒng)的性能。該論文重點(diǎn)分析了KMP算法的實(shí)現(xiàn)原理和C語言實(shí)現(xiàn)，并在此基礎(chǔ)上提出了改進(jìn)的KMP算法，使得該算法更方便實(shí)用。關(guān)鍵詞：KMP算法；時間復(fù)雜度；串匹配；改進(jìn)；方便使用；StringmatchingalgorithmandImplementationoftheProgramCollegeofComputerSciences,ComputerScienceandTechnologyProfessionalAbstractor:Amongthestringmatchingalgorithm,theoldestandmostfamousisKMPalgorithmco-sponsoredbyD.EKnuth,J.h.Morris,VRPrattin1997.Asoftoday,alotofresearchtoStringmatchingarestillinprogress,toseekamoresimplyorbetteraveragetimecomplexityofthealgorithm.Indifferentresearchdirection,scholarshavedesignedalotofvalidmatching.Inreallife,thestringmatchingtechniqueiswidelyused，Themainareasinclude:intrusiondetection,virusdetection,informationretrieval,informationfiltering,computationalbiology,financialinspectionandsoon.Inmanyapplications，alargepercentageofthetimewasplacedbythestringmatching,sothestringmatchingalgorithmssignificantlyaffectthespeedperformanceofthewholesystem.ThepaperanalyzestheimplementationoftheKMPalgorithmtheoryandthroughtheClanguagetoachieveit.AndweputsforwardamodifiedKMPalgorithminordertomakesthealgorithmmoreconvenientandpractical.Keywords:KMPalgorithm;Timecomplexity;Stringmatching;Improved;Easytouse;目錄摘要﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒1ABSTRACT﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒1引言﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒3第一節(jié)：字符串匹配研究的目的和意義﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒3第二節(jié)：本文的內(nèi)容和安排﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒3串匹配算法的概念與研究現(xiàn)狀﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒4第一節(jié)：字符串匹配的有關(guān)概念﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒4第二節(jié)：字符串匹配算法的研究現(xiàn)狀﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒4第三章KMP算法和BM算法及其改進(jìn)算法的研究及實(shí)現(xiàn)﹒﹒﹒﹒﹒﹒5 第一節(jié)：KMP算法的研究及實(shí)現(xiàn)﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒5 第二節(jié)：KMP算法改進(jìn)及其程序?qū)崿F(xiàn)﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒8第四章總結(jié)和展望﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒12第一節(jié)：總結(jié)﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒13第二節(jié)：展望﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒13參考文獻(xiàn)﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒14致謝﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒﹒14 第一章：引言第一節(jié)：字符串匹配研究的目的和意義字符串是計(jì)算機(jī)科學(xué)中常見的基本概念，搜索問題也是計(jì)算機(jī)科學(xué)中的基本問題。而且迄今為止文本信息仍然還是最主要的信息交換手段之一，因此作為文本處理中的一個重要領(lǐng)域——字符串匹配，就顯得尤其的重要，隨著互聯(lián)網(wǎng)的日漸龐大，信息也是越來越多，如何在海量的信息中快速查找自己所要的信息是網(wǎng)絡(luò)搜索研究的熱點(diǎn)所在；在這其中，字符串匹配算法起著非常重要的作用，一個高效的字符串匹配算法，可以極大的提高搜索的效率和質(zhì)量。本文力圖闡明字符串匹配算法的發(fā)展過程中的兩個重要的算法KMP算法和BM算法，并且并介紹了各個算法的特點(diǎn)，并給予了適當(dāng)?shù)谋容^和分析，進(jìn)而提出了新的字符串匹配算法希望能夠在各方面有所改進(jìn)。字符串匹配技術(shù)有著十分廣泛的應(yīng)用領(lǐng)域，它的最直接的應(yīng)用領(lǐng)域是構(gòu)建數(shù)據(jù)的全文檢索系統(tǒng)和圖書文獻(xiàn)目錄摘要的查詢系統(tǒng)。尤其在近年來，網(wǎng)絡(luò)技術(shù)馬不停蹄的快速發(fā)展，網(wǎng)絡(luò)帶寬不斷增加，隨之出現(xiàn)的問題也越來越多，加之隨著網(wǎng)絡(luò)技術(shù)和生物技術(shù)的不斷發(fā)展，串模式匹配技術(shù)又在網(wǎng)絡(luò)安全，網(wǎng)絡(luò)信息檢索和生物計(jì)算等領(lǐng)域中發(fā)揮著重要作用，并不斷發(fā)展。而且在對大量黃色信息，反動言論和國家機(jī)密的過濾方面以及入侵檢測技術(shù)和內(nèi)容過濾技術(shù)方面字符串匹配算法也扮演者一個不可或缺的角色。隨著生命科學(xué)技術(shù)的發(fā)展，人們對生命物質(zhì)的微觀結(jié)構(gòu)的認(rèn)識越來越清晰。而且人類基因組序列的繪制工作目前己經(jīng)完成。計(jì)算生物學(xué)中的一個最基本問題是，尋找一個或一組基因片斷在一個基因序列中的出現(xiàn)位置，以比較基因的相似性和遺傳關(guān)系；或者根據(jù)己知的蛋白質(zhì)樣本去匹配未知的蛋白質(zhì)序列，來確定這種未知的蛋白質(zhì)序列所屬蛋白質(zhì)的種類和功能。由于蛋白質(zhì)和基因都可以使用建立在一定字符集上的符號序列來表示，因而傳統(tǒng)的字符串匹配技術(shù)又有了新的發(fā)揮之地。尤其是近些年來的發(fā)展，科學(xué)家們對基因發(fā)生的突變和進(jìn)化等變化進(jìn)行研究，來描述同一物種的基因序列可能存在一定的差別，所以這就促進(jìn)了“近似匹配”技術(shù)的又一提高和發(fā)展。綜上所述，字符串匹配技術(shù)在眾多的領(lǐng)域中發(fā)揮著基礎(chǔ)的核心作用，對字符串匹配算法作進(jìn)一步的研究和改進(jìn)，對于提高執(zhí)行的效率、增加應(yīng)用系統(tǒng)的性能、節(jié)約硬件成本等有著重要的現(xiàn)實(shí)意義。第二節(jié)：本文的內(nèi)容和安排本文通過對經(jīng)典字符串匹配算法的深入理解和分析，在KMP算法的基礎(chǔ)上提出了兩種改進(jìn)算法，并且給出了程序?qū)崿F(xiàn)代碼，經(jīng)過分析和測試確定其性能得到提高，在某些方面都達(dá)到了較高的水平。本文的后續(xù)的章節(jié)安排為：第二章將對字符串匹配算法的概念進(jìn)行歸納并總結(jié)其研究現(xiàn)狀；第三章詳細(xì)分析字符串匹配算法：KMP算法，并提出相應(yīng)的新的改進(jìn)算法，而且深入分析所涉及到的經(jīng)典算法的思想以及程序的實(shí)現(xiàn)方法，并且將改進(jìn)后的算法與之比較，得出改進(jìn)后算法的優(yōu)點(diǎn)。最后第四章進(jìn)行總結(jié)和展望。第二章串匹配算法的概念與研究現(xiàn)狀第一節(jié)：字符串匹配的有關(guān)概念字符串是n(0)個字符的有限序列，記作S:“c0c1c2…cn-1”。其中，S是串名字；“c0c1c2…cn-1”是串值；ci是串中字符；n是串的長度。如：“WelcometoLinuxworld!!!”模式匹配是串的基本運(yùn)算之一。它是指在串中尋找子串（第一個字符）在串中的位置。有兩個字符串T和Ｓ，字符串T稱為正文，字符串S稱為模式，要求找出模式S在正文T中的首次出現(xiàn)的位置。一旦模式S在正文T中找到，就說發(fā)生一次匹配。有些應(yīng)用可能會要求找出所有的匹配位置。算法復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度。其作用：時間復(fù)雜度是度量算法執(zhí)行的時間長短；而空間復(fù)雜度是度量算法所需存儲空間的大小。KMP字符串模式匹配通俗點(diǎn)說就是一種在一個字符串中定位另一個串的高效算法。簡單匹配算法的時間復(fù)雜度為O(m*n);KMP匹配算法的時間復(fù)雜度為O(m+n).第二節(jié)：字符串匹配算法的研究現(xiàn)狀近年來，學(xué)術(shù)界的興趣與日俱增，特別在生物信息學(xué)和信息檢索兩個領(lǐng)域中，需要處理的文本規(guī)模越來越大，而且需要在文本中進(jìn)行越來越復(fù)雜的搜索。因此，出現(xiàn)了一種非標(biāo)準(zhǔn)的模式匹配問題,該問題涵蓋的內(nèi)容包括通配符、近似匹配等等。近期，學(xué)術(shù)界最活躍的問題之一就是研究帶有通配符的串匹配問題。即帶有don'tcare或wildcard字符。然而，通配符的引入會讓問題定義更加靈活，卻也帶來了復(fù)雜性。算法的設(shè)計(jì)有時不僅僅考慮時空效率，保證匹配結(jié)果的完備性很可能成為算法設(shè)計(jì)更重要的問題。在串匹配研究領(lǐng)域中，一個人所共知的事實(shí)是“算法的思想越簡單，實(shí)際應(yīng)用的效果越好”。另外，隨著新一代計(jì)算機(jī)的產(chǎn)生，會出現(xiàn)一些新技術(shù)，例如位并行等。然而KMP算法依然占據(jù)著不可替代的作用，尤其是他們的優(yōu)化版更是應(yīng)用廣泛。第三章：KMP算法和BM算法及其改進(jìn)算法的研究及實(shí)現(xiàn)第一節(jié)：KMP算法的研究及實(shí)現(xiàn)KMP算法是一種線性時間復(fù)雜的字符串匹配算法，它是對BF算法（Brute-Force，最基本的字符串匹配算法的）改進(jìn)。由D.E.Knuth與V.R.Pratt和J.H.Morris同時發(fā)現(xiàn)，因此人們稱它為克努特——莫里斯——普拉特操作（簡稱KMP算法）。KMP算法的關(guān)鍵是根據(jù)給定的模式串W1,m,定義一個next函數(shù)。next函數(shù)包含了模式串本身局部匹配的信息。首先，我們引入一個叫失敗鏈接值(faillink)的概念，就是說“每當(dāng)一趟匹配過程中出現(xiàn)字符比較不等時，不需回溯i指針，而是利用已經(jīng)得到的‘部分匹配’結(jié)果（匹配串的每個字符的失敗鏈接值）將模式（匹配子串）向右‘滑動’盡可能遠(yuǎn)的一段距離，繼續(xù)進(jìn)行比較?！逼鋵?shí)質(zhì)失敗鏈接值就是一個和主串完全無關(guān)只和子串相關(guān)的值。當(dāng)子串某一位和主串“失配”了（其實(shí)這句話還應(yīng)該理解為到子串這一位前面的都和主串“相配”），則跳到失敗鏈接值的那一位上去（簡稱失敗鏈接位），使得失敗鏈接位上的那個字符繼續(xù)和主串當(dāng)前字符進(jìn)行比較，如果不匹配再跳到失敗鏈接位的失敗鏈接位上去，如果還不匹配就接著往前跳，一直跳到某一位和主串目前位置上的字符相同或者跳到子串最開頭為止。而這個失敗鏈接位是怎么求出來的呢，舉個例子來說，子串為"aac"，我們現(xiàn)在要求的是'c'這一位(j=2)所對應(yīng)的失敗鏈接值，也就是說，'c'前面部分即"aa"已經(jīng)和主串相配了，而'c'沒能和主串相配，那么要跳到前面的哪一位上去呢，假設(shè)主串是"aaab"(綠色部分的aa已經(jīng)確定)，那么，子串只要向右移動1位即做到如下對應(yīng)即可:主串： aaa

b

aaab字串： aac

——>

aac｜｜｜位置： 0 12 也就是在0~j-1之間(在這兒是0~1之間)找到一個數(shù)k(在這里是1)，使得'c'前面k位字符串和子串的第k位前面k位字符串相等,這么一來就能保證在子串向右移動（也就是k指針向子串左邊的錯誤鏈接位跳）了之后仍然有k指針指向的那一位前面的k長度部分的字符串和j指針指向的那一位前面的k長度部分的字符串即主串i指針指向的那一位前面的k長度部分的字符串相同,這也正是移動后(即j跳到k所指位置后)仍能保證j前面部分和主串i前面相同長度部分字符串相同的必要條件。這個k的值也就成為了j的失敗鏈接值(即flink[j]=k)，k所對應(yīng)的位置就成了j所對應(yīng)位置的失敗鏈接位.。如果錯誤鏈接位上字符和當(dāng)前位上字符相同的話，可以直接讓當(dāng)前位的錯誤鏈接值等于錯誤鏈接位的錯誤鏈接值(當(dāng)然都是就子串來說的)，這樣可以將程序更加優(yōu)化。求s的各字符的失敗鏈接值算法：引入數(shù)組next[]，元素個數(shù)為S的長度，依次存放S各字符的失敗鏈接值。先置next[0]=-1，在已求得next[0]，…，next[j-1]的情況下，求next[j].如next[j-1]=k,又有s[k]=s[j-1]，那末置next[j]為next[j-1]+1;如果s[k]≠s[j-1]，令k1=next[k],如有s[k1]=s[j-1],則置next[j]為k1+1;如果s[k1]≠s[j-1],則按s[k1]的失敗鏈接值再繼續(xù)尋找，直至找到一個失敗鏈接值kn,使得s[kn]=s[j-1]，或者kn=-1，這時就置next[j]=kn+1。尋找模式各字符失敗鏈接值的函數(shù)：voidfaillink(char*s,intnext[]){intj,k;next[0]=-1;for(j=1;s[j]!='\0';j++){k=next[j-1];while(k!=-1&&s[k+1]!=s[j])k=next[k];if(s[j]==s[k+1])next[j]=k+1;elsenext[j]=-1;}}具體的KMP算法C語言實(shí)現(xiàn)代碼如下:假設(shè)又兩個隨機(jī)的字符串S和T，例如主串S=acdfgawedgawekmah和子串T=gawek，則由此可知其其匹配的起始下標(biāo)為10。#include<stdio.h>#include<string.h>#defineN50voidGetNext(chart[],intnext[]){ next[1]=0; intj=1,k=0,h; h=strlen(t); while(j<h) if((k==0)||(t[j]==t[k])) { j++; k++; next[j]=k;break; } elsek=next[k];}voidmain(){printf("姓名李春豹學(xué)號200713140114\n"); chars[N],t[N]; intnext[N]={0}; printf("請輸入主串s:\n"); gets(s); printf("請輸入模式串t:\n"); gets(t); inti=1,j=1,k=strlen(s)-1,h=strlen(t)-1; while((i<=k)&&(j<=h)) { if(s[i]==t[j]) { i++; j++; } else { GetNext(t,next); j=next[j]; {if(j==0) { i++; j++; }} } } if(j>h) printf("匹配的起始下表為:%d\n",i-j+1); else printf("匹配失敗\n");}執(zhí)行結(jié)果見下面的截圖：第二節(jié)：KMP算法改進(jìn)及其程序?qū)崿F(xiàn)根據(jù)上一節(jié)的學(xué)習(xí)，我們知道KMP算法是在一直串模式的next函數(shù)值的基礎(chǔ)上執(zhí)行的，那么如何求得模式串的next函數(shù)值呢？首先我們來了解下next數(shù)組的含義：令原始串為:S[i]，其中0<=i<=n；模式串為:T[j]，其中0<=j<=m。假設(shè)目前匹配到如下位置S0,S1,S2,...,Si-j,Si-j+1,Si-1,Si,Si+1,,Sn

T0,T1,,Tj-1,Tj,S和T的紅色部分匹配成功，恰好到Si和Tj的時候失配（粉紅色），如果要保持i不變，同時達(dá)到讓模式串T相對于原始串S右移的話，可以更新j的值，讓Si和新的Tj進(jìn)行匹配，假設(shè)新的j用next[j]表示，即讓Si和next[j]匹配，顯然新的j值要小于之前的j值，模式串才會是右移的效果，也就是說應(yīng)該有next[j]<=j-1。那新的j值也就是next[j]應(yīng)該是多少呢？我們觀察如下的匹配：（1）.如果模式串右移1位，即next[j]=j-1，

即讓綠色的Si和Tj-1匹配

(注：省略號為未匹配部分)S0,S1,S2,...,Si-j,Si-j+1,Si-1,Si,Si+1,,Sn

T0,T1,,..Tj-1,Tj,...(T的劃線部分和S劃線部分相等<1>)

T0,T1,Tj-2,Tj-1,

...(移動后的T的劃線部分和S的劃線部分相等<2>)根據(jù)<1><2>可以知道當(dāng)next[j]=j-1，即模式串右移一位的時候，有T[0~j-2]==T[1~j-1]。而這兩部分恰好是字符串T[0~j-1]的前綴和后綴，也就是說next[j]的值取決于模式串T中j前面部分的前綴和后綴相等部分的長度。(2).如果模式串右移2位，即next[j]=j-2，

即讓綠色的Si和Tj-2匹配

S0,S1,...,Si-j,Si-j+1,Si-j+2,Si-1,Si,Si+1,,Sn

T0,T1,T2,,Tj-1,Tj,(T的劃線部分和S劃線部分相等<3>)

T0,T1,,Tj-3,Tj-2,(移動后的T的劃線部分和S的劃線部分相等<4>)同樣根據(jù)<3><4>可以知道當(dāng)next[j]=j-2，即模式串右移兩位的時候，有T[0~j-3]==T[2~j-1]。而這兩部分也恰好是字符串T[0~j-1]的前綴和后綴，也就是說next[j]的值取決于模式串T中j前面部分的前綴和后綴相等部分的長度。（3）.依次類推，可以得到如下結(jié)論當(dāng)發(fā)生失配的情況下，j的新值next[j]取決于模式串中T[0~j-1]中前綴和后綴相等部分的長度，并且恰好next[j]等于這個最大長度。因而我們進(jìn)而得到求出該數(shù)組的算法為：voidget_nextval(SStringT,intnextval[]){//將模式串T的next函數(shù)值并存入數(shù)組nextval中inti=1;nextval[1]=0;j=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[j];}//get_nextval進(jìn)而我們得到KMP算法的匹配函數(shù)如下：Char*kmpMatch(char*t,char*s,intnext[]){intk,j;k=j=0;while(s[j]!='\0'&&t[k]!='\0') if(s[j]==t[k]){k++;j++;} elseif(j==0)k++; elsej=next[j-1]+1;if(s[j]=='\0')returnt+k-j;returnNULL;}我們研究的目的是經(jīng)過對KMP算法的改進(jìn)可以實(shí)現(xiàn)對主字符串中的所有字串出現(xiàn)的匹配點(diǎn)都找出來，并且統(tǒng)計(jì)其各自的匹配的起始下標(biāo)。具體的改進(jìn)后的KMP算法C語言實(shí)現(xiàn)的源代碼如下：假設(shè)又兩個隨機(jī)的字符串S和T，例如主串S=acdfgawedgawekmagawekacdgegegawekbmahbn和子串T=gawek;#include<iostream.h>#include<string.h>#include<stdio.h>#defineN50voidfaillink(char*t,int*flink){intj,k=-1;intlent=strlen(t);flink[0]=-1;for(j=0;j<lent-1;j++){while((k!=-1)&&(t[j]!=t[k])){k=flink[k];}flink[j+1]=k+1;k++;}}intindex(char*s,char*t,int*p){inti,j=0,tot=0;int*flink=newint[strlen(t)];faillink(t,flink);intlens=strlen(s);intlent=strlen(t);for(i=0;i<lens;){while((j!=-1)&&(s[i]!=t[j])){j=flink[j];}j++;i++;if(j==lent){p[tot]=i-j;tot++;i--;j--;j=flink[j];}}delete[]flink;return(tot);}intmain(){printf("姓名李春豹學(xué)號200713140114\n"); chara[N],b[N]; intnext[N]={0}; printf("請輸入主串a(chǎn):\n"); gets(a); printf("請輸入模式串b:\n"); gets(b);intp[50];inttot;tot=index(a,b,p);cout<<"主串："<<a<<endl;cout<<"子串："<<b<<endl<<endl;cout<<"匹配數(shù)目："<<tot<<endl;if(tot!=0){cout<<"匹配位置：";for(inti=0;i<tot;i++){cout<<p[i]<<"\t";}cout<<endl;}cout<<endl;return(0);}執(zhí)行結(jié)果見下面的截圖：通過以上改進(jìn)使我們的KMP算法的功能更復(fù)雜更強(qiáng)大，能夠在一個字符串中輕易的找到你想查找的字符串，更方便、更實(shí)用。例如給我一個主串和其他多字符串，問哪些字符串是這個主串的子串，這些問題在以后的軟件開發(fā)中用到的話就可以直接拿去用，實(shí)在是很方便。因?yàn)槲蚁雡indows中的搜索引擎的查找功能是不是也運(yùn)用了這種算法呢，只要輸入某篇文章中的幾個關(guān)鍵字，就能很快的搜索出它是什么文章，這不是和我們的簡單的字符串查找很相似嘛。第四章：總結(jié)與展望第一節(jié)：總結(jié)KMP算法，即Knuth-Morris-Pratt算法，是一種典型的基于前綴的搜索的字符串匹配算法。KMP算法的搜索思路應(yīng)該算是比較簡單的：模式和文件進(jìn)行前綴匹配，一旦發(fā)現(xiàn)不匹配的現(xiàn)象，則通過一個精心構(gòu)造的數(shù)組索引模式向前滑動的距離。這個算法相對于常規(guī)的逐個字符匹配的方法的優(yōu)越之處在于，它可以通過數(shù)組索引，減少匹配的次數(shù)，從而提高運(yùn)行效率。掌握了KMP算法就明白了各個搜索引擎工作的工作原理，都是通過字符串匹配來實(shí)現(xiàn)迅速查找的，迅速、準(zhǔn)確。 我不會忘記這難忘的幾個月的時間。畢業(yè)論文的制作給了我難忘的回憶。在我徜徉書海查找資料的日子里，面對無數(shù)書本的羅列，最難忘的是每次找到資料時的激動和興奮在整個過程中，我學(xué)到了新知識，增長了見識。在今后的日子里，我仍然要不斷地充實(shí)自己，爭取在所學(xué)領(lǐng)域有所作為。腳踏實(shí)地，認(rèn)真嚴(yán)謹(jǐn)，實(shí)事求是的學(xué)習(xí)態(tài)度，不怕困難、堅(jiān)持不懈、吃苦耐勞的精神是我在這次設(shè)計(jì)中最大的收益。我想這是一次意志的磨練，是對我實(shí)際能力的一次提升，也會對我未來的學(xué)習(xí)和工作有很大的幫助。第二節(jié)：展望字符串匹配算法在網(wǎng)絡(luò)安全，網(wǎng)絡(luò)信息檢索和生物計(jì)算等領(lǐng)域中的應(yīng)用十分的廣泛和普遍，而且是至關(guān)重要不可或缺的，在未來的世界里她的作用會越來越大，而且人們會不斷的改進(jìn)她的算法執(zhí)行思想和實(shí)現(xiàn)方法，以達(dá)到更高效、更靈敏、更迅速的目的，最大限度的造福人類。在我們的生活中就有無數(shù)的字符串匹配方面的應(yīng)用，電話信號的接收，windows系統(tǒng)中的查找功能，搜索引擎等等，都是她的應(yīng)用范圍。在查找打擊各種黃色網(wǎng)站和暴力網(wǎng)站的查封都需要用到字符串匹配的技術(shù)。在以后的生活中字符串的應(yīng)用范圍會更加廣泛，在世界的任何一個角落，任何一個時候我們都會用到匹配的技術(shù)，將與人們的生活息息相關(guān)。參考文獻(xiàn)：[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京:清華大學(xué)出版社，2008.9[2]劉燕兵.串匹配算法優(yōu)化的研究.中國科學(xué)院碩士學(xué)位論文-中國科學(xué)院計(jì)算技術(shù)研究所,2006.6[3]潘金貴，顧鐵成.算法導(dǎo)論.[M].機(jī)械工業(yè)出版社，2010.9[4]吳哲輝，曹立明，蔣昌俊.算法分析與設(shè)計(jì)[M].北京:煤炭工業(yè)出版社，2006.6致謝 時光匆匆如流水，轉(zhuǎn)眼便是大學(xué)畢業(yè)時節(jié)，春夢秋云，聚散真的好快啊。離校的日期已經(jīng)日益臨近了，畢業(yè)論文的完成也隨之進(jìn)入尾聲。從開始進(jìn)入課題到論文的順利完成一直都離不開老師、同學(xué)、朋友給我的熱情幫助和耐心的教導(dǎo)，在這里請接受我最誠摯的謝意。本學(xué)位論文的撰寫都是由滕云老師的親切關(guān)懷和悉心指導(dǎo)下完成的。從課題的選擇到論文的最終完成，滕老師都給了我細(xì)心的指導(dǎo)和不懈的支持，并且耐心指導(dǎo)論文之余還不忘拓寬我們的文化視野，讓我對現(xiàn)在非常熱門的云技術(shù)有所了解。滕老師宅心仁厚，閑靜少言，不慕榮利，對學(xué)生認(rèn)真負(fù)責(zé)，在他身上，我們可以感受到一個學(xué)者的嚴(yán)謹(jǐn)和務(wù)實(shí)，這些都讓我們獲益匪淺，并且將終生受用無窮。畢竟“經(jīng)師易得，人師難求”，希望借此機(jī)會向滕老師表示最衷心的感謝！此外，本文得以順利完成，也是得到了計(jì)算機(jī)學(xué)院的其它老師的幫助，他們在我論文撰寫的過程中給予了我很多的指導(dǎo)，再次同樣感謝他們。最后要感謝的我的父母，他們不辭辛苦供我讀書，讓我在漫漫的人生旅途中有了更多的良師益友和更深層的知識積累。在未來的日子里，我會更加努力的學(xué)習(xí)和工作，不辜負(fù)父母對我的殷殷希望！我一定會好好孝敬和報(bào)答他們的?；贑8051F單片機(jī)直流電動機(jī)反饋控制系統(tǒng)的設(shè)計(jì)與研究基于單片機(jī)的嵌入式Web服務(wù)器的研究MOTOROLA單片機(jī)MC68HC（8）05PV8/A內(nèi)嵌EEPROM的工藝和制程方法及對良率的影響研究基于模糊控制的電阻釬焊單片機(jī)溫度控制系統(tǒng)的研制基于MCS-51系列單片機(jī)的通用控制模塊的研究基于單片機(jī)實(shí)現(xiàn)的供暖系統(tǒng)最佳啟停自校正（STR）調(diào)節(jié)器單片機(jī)控制的二級倒立擺系統(tǒng)的研究基于增強(qiáng)型51系列單片機(jī)的TCP/IP協(xié)議棧的實(shí)現(xiàn)基于單片機(jī)的蓄電池自動監(jiān)測系統(tǒng)基于32位嵌入式單片機(jī)系統(tǒng)的圖像采集與處理技術(shù)的研究基于單片機(jī)的作物營養(yǎng)診斷專家系統(tǒng)的研究基于單片機(jī)的交流伺服電機(jī)運(yùn)動控制系統(tǒng)研究與開發(fā)基于單片機(jī)的泵管內(nèi)壁硬度測試儀的研制基于單片機(jī)的自動找平控制系統(tǒng)研究基于C8051F040單片機(jī)的嵌入式系統(tǒng)開發(fā)基于單片機(jī)的液壓動力系統(tǒng)狀態(tài)監(jiān)測儀開發(fā)模糊Smith智能控制方法的研究及其單片機(jī)實(shí)現(xiàn)一種基于單片機(jī)的軸快流CO〈,2〉激光器的手持控制面板的研制基于雙單片機(jī)沖床數(shù)控系統(tǒng)的研究基于CYGNAL單片機(jī)的在線間歇式濁度儀的研制基于單片機(jī)的噴油泵試驗(yàn)臺控制器的研制基于單片機(jī)的軟起動器的研究和設(shè)計(jì)基于單片機(jī)控制的高速快走絲電火花線切割機(jī)床短循環(huán)走絲方式研究基于單片機(jī)的機(jī)電產(chǎn)品控制系統(tǒng)開發(fā)基于PIC單片機(jī)的智能手機(jī)充電器基于單片機(jī)的實(shí)時內(nèi)核設(shè)計(jì)及其應(yīng)用研究基于單片機(jī)的遠(yuǎn)程抄表系統(tǒng)的設(shè)計(jì)與研究基于單片機(jī)的煙氣二氧化硫濃度檢測儀的研制基于微型光譜儀的單片機(jī)系統(tǒng)單片機(jī)系統(tǒng)軟件構(gòu)件開發(fā)的技術(shù)研究基于單片機(jī)的液體點(diǎn)滴速度自動檢測儀的研制基于單片機(jī)系統(tǒng)的多功能溫度測量儀的研制基于PIC單片機(jī)的電能采集終端的設(shè)計(jì)和應(yīng)用基于單片機(jī)的光纖光柵解調(diào)儀的研制氣壓式線性摩擦焊機(jī)單片機(jī)控制系統(tǒng)的研制基于單片機(jī)的數(shù)字磁通門傳感器基于單片機(jī)的旋轉(zhuǎn)變壓器-數(shù)字轉(zhuǎn)換器的研究基于單片機(jī)的光纖Bragg光柵解調(diào)系統(tǒng)的研究單片機(jī)控制的便攜式多功能乳腺治療儀的研制基于C8051F020單片機(jī)的多生理信號檢測儀基于單片機(jī)的電機(jī)運(yùn)動控制系統(tǒng)設(shè)計(jì)Pico專用單片機(jī)核的可測性設(shè)計(jì)研究基于MCS-51單片機(jī)的熱量計(jì)基于雙單片機(jī)的智能遙測微型氣象站MCS-51單片機(jī)構(gòu)建機(jī)器人的實(shí)踐研究基于單片機(jī)的輪軌力檢測基于單片機(jī)的GPS定位儀的研究與實(shí)現(xiàn)基于單片機(jī)的電液伺服控制系統(tǒng)用于單片機(jī)系統(tǒng)的MMC卡文件系統(tǒng)研制基于單片機(jī)的時控和計(jì)數(shù)系統(tǒng)性能優(yōu)化的研究基于單片機(jī)和CPLD的粗光柵位移測量系統(tǒng)研究單片機(jī)控制的后備式方波UPS提升高職學(xué)生單片機(jī)應(yīng)用能力的探究基于單片機(jī)控制的自動低頻減載裝置研究基于單片機(jī)控制的水下焊接電源的研究基于單片機(jī)的多通道數(shù)據(jù)采集系統(tǒng)基于uPSD3234單片機(jī)的氚表面污染測量儀的研制基于單片機(jī)的紅外測油儀的研究96系列單片機(jī)仿真器研究與設(shè)計(jì)基于單片機(jī)的單晶金剛石刀具刃磨設(shè)備的數(shù)控改造基于單片機(jī)的溫度智能控制系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)基于MSP430單片機(jī)的電梯門機(jī)控制器的研制基于單片機(jī)的氣體測漏儀的研究基于三菱M16C/6N系列單片機(jī)的CAN/USB協(xié)議轉(zhuǎn)換器基于單片機(jī)和DSP的變壓器油色譜在線監(jiān)測技術(shù)研究基于單片機(jī)的膛壁溫度報(bào)警系統(tǒng)設(shè)計(jì)基于AVR單片機(jī)的低壓無功補(bǔ)償控制器的設(shè)計(jì)基于單片機(jī)船舶電力推進(jìn)電機(jī)監(jiān)測系統(tǒng)基于單片機(jī)網(wǎng)絡(luò)的振動信號的采集系統(tǒng)基于單片機(jī)的大容量數(shù)據(jù)存儲技術(shù)的應(yīng)用研究基于單片機(jī)的疊圖機(jī)研究與教學(xué)方法實(shí)踐基于單片機(jī)嵌入式Web服務(wù)器技術(shù)的研究及實(shí)現(xiàn)基于AT89S52單片機(jī)的通用數(shù)據(jù)采集系統(tǒng)基于單片機(jī)的多道脈沖幅度分析儀研究機(jī)器人旋轉(zhuǎn)電弧傳感角焊縫跟蹤單片機(jī)控制系統(tǒng)基于單片機(jī)的控制系統(tǒng)在PLC虛擬教學(xué)實(shí)驗(yàn)中的應(yīng)用研究基于單片機(jī)系統(tǒng)的網(wǎng)絡(luò)通信研究與應(yīng)用基于PIC16F877單片機(jī)的莫爾斯碼自動譯碼系統(tǒng)設(shè)計(jì)與研究基于單片機(jī)的模糊控制器在工業(yè)電阻爐上的應(yīng)用研究基于雙單片機(jī)沖床數(shù)控系統(tǒng)的研究與開發(fā)基于Cygnal單片機(jī)的μC/OS-Ⅱ的研究基于單片機(jī)的一體化智能差示掃描量熱儀系統(tǒng)研究基于TCP/IP協(xié)議的單片機(jī)與Internet互聯(lián)的研究與實(shí)現(xiàn)變頻調(diào)速液壓電梯單片機(jī)控制器的研究基于單片機(jī)γ-免疫計(jì)數(shù)器自動換樣功能的研究與實(shí)現(xiàn)基于單片機(jī)的倒立擺控制系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)單片機(jī)嵌入式以太網(wǎng)防盜報(bào)警系統(tǒng)基于51單片機(jī)的嵌入式Internet系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)單片機(jī)監(jiān)測系統(tǒng)在擠壓機(jī)上的應(yīng)用HYPERLINK"/detail.htm