數(shù)據(jù)結(jié)構(gòu)-KMP算法的實(shí)現(xiàn)

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目:模式匹配中的KMP算法的實(shí)現(xiàn)專業(yè)：計(jì)算機(jī)科技院系：計(jì)算機(jī)學(xué)院姓名：ｘxxxxxｘx學(xué)號(hào):xxxｘxｘｘ時(shí)間:20１３年9月22日目錄TOＣ＼ｏ＂1－2"\ｈ\uＨYPERLIＮK＂Ｃ:\\ＤocumeｎtsanｄSettinｇs\\Aｄminｉｓtｒatoｒ＼＼桌面\\畢業(yè)設(shè)計(jì)\\參考文獻(xiàn)＼＼數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.doc"\l＂_Ｔｏｃ９734"1需求分析 3HYＰＥRLINK"C:\＼DoｃumentｓandＳettiｎｇｓ\＼Admｉnｉstrａt(yī)ｏr\＼桌面\\畢業(yè)設(shè)計(jì)\\參考文獻(xiàn)\\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.ｄoc"\l"＿Ｔｏc2228８"1.1問(wèn)題描述?3HYPERＬINK＂C:\\DｏcumｅntsaｎdSettings＼＼Adminisｔｒatｏｒ＼\桌面\\畢業(yè)設(shè)計(jì)\＼參考文獻(xiàn)\\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.doc"\ｌ"_Toc19９３9"1.2基本要求?３HYPＥRLINK"C:\\DoｃumｅntsaｎdSettinｇｓ\\Adminiｓtraｔoｒ＼＼桌面\\畢業(yè)設(shè)計(jì)\\參考文獻(xiàn)\\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.doc"\ｌ＂_Toc143４4＂2概要設(shè)計(jì)?3HYPERLINK＂C：\\DoｃumeｎtsaｎdSettings\＼Admiｎistrator\＼桌面\＼畢業(yè)設(shè)計(jì)＼\參考文獻(xiàn)\\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.ｄoc"＼l"＿Toc2１57"3詳細(xì)設(shè)計(jì) 5ＨYＰERLINK"C:＼＼DocuｍeｎｔsandSｅｔtｉngｓ＼＼Ａdminｉｓtrator\\桌面\＼畢業(yè)設(shè)計(jì)\＼參考文獻(xiàn)\＼數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.doc"＼l＂_Toc150２8"3．１為主串和模式串賦值 5ＨYPERＬＩNＫ＂Ｃ：\\ＤoｃｕmentsandSeｔｔinｇs\\Ａdmｉniｓtratoｒ＼＼桌面\\畢業(yè)設(shè)計(jì)＼\參考文獻(xiàn)＼\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.doc"\l＂_Toc2475"3．2利用Output（)函數(shù)輸出串。?PAGＥＲEF_Toc２４７5-５HYPEＲＬINK＂C:＼\DｏcｕmentｓandSettｉｎｇs＼\Ａdｍｉnistrator\\桌面\\畢業(yè)設(shè)計(jì)＼＼參考文獻(xiàn)\\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.doc＂\ｌ"_Toc１５05６"３.３求各串的長(zhǎng)度 ６HYPERLＩNK"C:＼＼DoｃuｍentｓanｄSｅttings\\Admiｎistrａt(yī)or\\桌面＼＼畢業(yè)設(shè)計(jì)＼\參考文獻(xiàn)\\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.doc"＼ｌ＂＿Ｔoｃ７9２8"3.4求模式串的模式值next[］函數(shù)?６HＹＰERＬINK＂C:＼\DocuｍｅntsａndSettings＼\Admiｎistrator\\桌面\＼畢業(yè)設(shè)計(jì)\＼參考文獻(xiàn)\＼數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.doｃ"４測(cè)試與分析?7ＨＹＰEＲLINＫ"C：\\ＤocuｍentsａndSettings\＼Ａdｍiniｓtｒａｔor＼\桌面\\畢業(yè)設(shè)計(jì)\\參考文獻(xiàn)＼\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.ｄoc＂５總結(jié) 9HＹＰERLINＫ"C：\＼ＤocｕmentｓａｎdＳeｔtings\＼Adｍｉnｉstraｔor\\桌面＼\畢業(yè)設(shè)計(jì)\\參考文獻(xiàn)\\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.doｃ"\ｌ"_Ｔoc193４2"６附錄:源程序清單 9ＨYPＥRＬINＫ"C：＼\DocumentsandＳettinｇs\＼Adｍｉnistrａｔｏr\\桌面＼\畢業(yè)設(shè)計(jì)\\參考文獻(xiàn)\\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告．doc＂＼l"_Toc2088６"參考文獻(xiàn) １31需求分析1.１問(wèn)題描述KMP算法是對(duì)一般模式匹配算法的改進(jìn),由Ｄ.E．Knuth與Ｖ.R.Pｒatt和J.H.Morｒis同時(shí)發(fā)現(xiàn)的因此人們稱它為克努特-莫里斯-莫拉特操作(簡(jiǎn)稱為KMP算法）。對(duì)于一般的模式匹配算法：分別利用兩個(gè)指針i和j指示主串S和T中的當(dāng)前正待比較的字符位置。算法的基本思想是:從主串的S的第ＰOＳ個(gè)字符開(kāi)始起和模式的第一個(gè)字符比較之,如相等，則繼續(xù)逐個(gè)比較后續(xù)字符；否則從主串的下一個(gè)字符起再重新和模式的字符比較之。以此類推，直到模式T中的每個(gè)字符依次和主串Ｓ中的一個(gè)連續(xù)字符序列相等,則稱匹配成功，則函數(shù)值為和模式Ｔ中的第一個(gè)字符相等的字符在主串S中的序號(hào)，否則稱匹配不成功，函數(shù)值為０.而對(duì)于模式匹配的ＫＭP算法可以在Ｏ（n＋m）的時(shí)間數(shù)量級(jí)上完成串的模式匹配操作。其改進(jìn)過(guò)程在于：每當(dāng)一趟匹配過(guò)程出現(xiàn)字符比較不相等時(shí)，不需回溯ｉ指針,而是利用已經(jīng)得到的部分匹配的結(jié)果將模式串向右滑動(dòng)一段盡可能遠(yuǎn)的距離后，繼續(xù)進(jìn)行比較?；瑒?dòng)的這一段距離我們將會(huì)用到函數(shù)Neｘt[],KMP算法的最大特點(diǎn)是指示主串的指針不須回溯,整個(gè)匹配過(guò)程中，對(duì)主串僅需從頭到尾掃描一遍,這對(duì)處理從外設(shè)輸入的龐大文件很有效，可以邊度入邊匹配，而無(wú)需回頭重讀。開(kāi)發(fā)工具:C語(yǔ)言1.2基本要求用C編寫一個(gè)程序?qū)崿F(xiàn)模式匹配的KＭP算法。要求對(duì)于任何輸入串Ａ,實(shí)現(xiàn)算法求next函數(shù)值；利用ｎexｔ函數(shù)值，實(shí)現(xiàn)串A在串B中的定位;若未搜索到，就返回0。首先要從鍵盤輸入主串Ｂ和模式串A，并采用用鏈?zhǔn)酱鎯?chǔ)，再根據(jù)Next()函數(shù)求模式串的Neｘt值，利用ＫMP算法進(jìn)行匹配，再用輸出函數(shù)輸出結(jié)果!２概要設(shè)計(jì)對(duì)該ｋｍp算法，定義的抽象數(shù)據(jù)類型如下：ADＴString{數(shù)據(jù)對(duì)象:D＝{ａｉ|ai∈ChaｒacterSet,i＝1，2,3，…,ｎ，n≥0｝數(shù)據(jù)關(guān)系:R1＝｛＜ai－1,ａi＞|ａｉ－1,ai∈Ｄ,ｉ=2，…,n}基本操作：ＳtrAｓsign(&T,chaｒｓ)初始條件：chaｒs是字符串常量。操作結(jié)果:生成一個(gè)其值等于chars的串T。StrCopy（S）初始條件:串S存在。操作結(jié)果：若S為空串，則返回TRUE,否則返回FＡLSE。StrLenｇｔh（S）初始條件：串Ｓ存在。操作結(jié)果：返回Ｓ元素的個(gè)數(shù),成為串的長(zhǎng)度。Ｉｎdeｘ(Ｓ,T,pos)初始條件:串Ｓ和Ｔ存在，Ｔ是非空串，1≤pos≤ＳtrLenｇｔh(S）.操作結(jié)果：若主串S中存在和串T相同的子串,則返回他在主串S中的第pｏs個(gè)字符之后第一次出現(xiàn)的位置；否則函數(shù)值為0。DeｓｔｏrｙSｔrｉnｇ(&Ｓ）初始條件：串S存在。操作結(jié)果:串S被銷毀。}ＡDTString該算法是對(duì)串進(jìn)行操作,對(duì)串的存儲(chǔ)結(jié)構(gòu)用線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示：typedefstructLＳｔriｎg{chaｒｄata;stｒuctLＳｔriｎg*next；}LSｔｒiｎg;該算法分為三個(gè)模塊:第一模塊[Ｉｎput(）函數(shù)]（利用該函數(shù)輸入主串和模式串）；第二模塊[Outpuｔ()函數(shù)利用該函數(shù)輸出串)。第三模塊[Leｎｇｔh（）](利用該函數(shù)求各串的長(zhǎng)度）；第四模塊[Ｇet_neｘt(）函數(shù)]（利用該函數(shù)求出模式串的next函數(shù)值）；第五模塊[Indｅx_KMP（)函數(shù)](利用該函數(shù)進(jìn)行主串和模式串之間的匹配);各個(gè)模塊之間的調(diào)用關(guān)系如下圖所示：圖２．1是對(duì)整個(gè)函數(shù)的流程圖。開(kāi)始開(kāi)始輸入A，B，pos調(diào)用Input函數(shù)存儲(chǔ)A，B調(diào)用Get_next函數(shù)對(duì)A,B執(zhí)行Length函數(shù)調(diào)用Index_KMP函數(shù)，并用Loc接收函數(shù)值調(diào)用Output輸出A，B，輸出LOC，Next結(jié)束整個(gè)函數(shù)的流程圖3詳細(xì)設(shè)計(jì)：3.1為主串和模式串賦值利用Inpuｔ（）函數(shù)輸入主串和模式串Ｉnｐｕｔ(）函數(shù)偽代碼:ＬStｒinｇ＊Ｉｎput（){ //通過(guò)標(biāo)準(zhǔn)輸入設(shè)備輸入串以鏈?zhǔn)酱鎯?chǔ)存儲(chǔ)數(shù)據(jù)并返回鏈的頭指針。?LＳｔrｉng*head，＊tail,*p；ｉnｔｃuｒｌen＝０;charch;hｅａｄ=(LStｒinｇ*)malloc(ｓiｚｅoｆ(ＬＳtring));//建立頭指針。if(！head）｛prｉntf（"存儲(chǔ)分配失敗")；eｘｉt(0);｝／/存儲(chǔ)分配失敗。scanf（"%c",&ch);ｗhile(ch！='\n'){p=（LＳｔrinｇ*）maｌｌoc(sizｅof(LＳtｒｉng）)；if（！p){ pｒintf("存儲(chǔ)分配失敗"）;ｅｘit(０);}/／存儲(chǔ)分配失敗。p->dａt(yī)ａ=ch；p-＞neｘt＝NULL;ｉｆ(cｕrlｅn=＝0)heａd->nexｔ＝p;ｅlｓe{tail－＞ｎｅxt=p;｝ｔａil＝ｐ；++curlen；hｅａd->ｄａｔa=curｌen;//用頭指針存儲(chǔ)串的長(zhǎng)度ｓｃanf("%c"，&ch)；}rｅtuｒnhead;}/／Inputｅ3．2利用Oｕtpｕｔ(）函數(shù)輸出串。ｖoidOutput（ＬSｔｒing*T){ //在標(biāo)準(zhǔn)輸出設(shè)備上輸出串T。ＬＳtriｎg＊p;p=T->next；while（ｐ!=ＮUＬＬ){printf("%c＂,p->data)；p=p－>ｎexｔ;}priｎｔf（"\ｎ"）;}//Ouｔｐut３.3求各串的長(zhǎng)度Lengtｈ（）函數(shù)求的各串的長(zhǎng)度，利用一個(gè)while循環(huán)語(yǔ)句，為后面的函數(shù)做好準(zhǔn)備工作；iｎtLengｔh(LStrｉｎg*T){ //求串T的長(zhǎng)度并返回其值。?intn=0;?LStriｎg*heａd;?ｈeaｄ＝Ｔ; ｉf（ｈead)n=heａｄ->data;rｅｔurｎn;｝／/Length3.4求模式串的模式值next[]函數(shù)用《模式匹配的KＭP算法》當(dāng)主串和模式串匹配不相等是,模式串應(yīng)向右移動(dòng)一段距離，此時(shí)我們需要得到模式串的next函數(shù)值。如何求next函數(shù),next函數(shù)值僅取決于模式本身而和主串無(wú)關(guān)。我們可以從分析nexｔ函數(shù)的定義出發(fā)用遞推的方法求得nexｔ函數(shù)值。由定義知：neｘt[１］=０設(shè)nｅｘt［j]=k，即有：＂ｔ１ｔ2…tｋ-1＂="ｔj-k＋1tj-ｋ+2…ｔｊ-1nexｔ[ｊ+1]=?可能有兩種情況:一種情況:若tk=tj則表明在模式串中這就是說(shuō)nｅxｔ[j＋1]=ｋ+1,即neｘt[j＋1]=ｎext[j］+1第二種情況:若tｋ≠tｊ則表明在模式串中ｔ１t2…tｋ＂≠＂tj-k+1tj－k+２…tj"此時(shí)可把求ｎexｔ函數(shù)值的問(wèn)題看成是一個(gè)模式匹配問(wèn)題,整個(gè)模式串既是主串又是模式,而當(dāng)前在匹配的過(guò)程中，已有（４.6)式成立,則當(dāng)tk≠tj時(shí)應(yīng)將模式向右滑動(dòng),使得第nexｔ［k］個(gè)字符和“主串”中的第ｊ個(gè)字符相比較。若next[k]=k′，且ｔk′=tｊ,則說(shuō)明在主串中第j＋1個(gè)字符之前存在一個(gè)最大長(zhǎng)度為k′的子串，使得＂t１ｔ2…ｔk′"=＂tj-k′+１tj-ｋ′+2…tj"此：next[ｊ+1]=next[k]＋1同理若tｋ′≠tｊ，則將模式繼續(xù)向右滑動(dòng)至使第ｎext[ｋ′］個(gè)字符和tj對(duì)齊，依此類推，直至tj和模式中的某個(gè)字符匹配成功或者不存在任何k′(1＜ｋ′<ｋ<…<j)滿足,此時(shí)若ｔ1≠tj＋1,則有:next[j+1]＝1否則若t１＝tｊ+1,則有:next[j+1]＝0綜上所述，求next函數(shù)值過(guò)程的偽碼算法如下：ｖoidＧeｔ_nexｔ(ＳＳtｒingＴ,ｉnｔｎext［]){ //求模式串T的ｎeｘt函數(shù)并存入數(shù)組nｅxt。i=1；nｅxt[1]=0;j=０;whilｅ（ｉ<t[０]）{if(j＝=０|｜ｔ[ｉ]==t[ｊ])｛＋+i;＋+j;nexｔ［i]=j；｝elsej=ｎexｔ[j］;｝}/／Get＿neｘt3．5模式匹配KMＰ算法的實(shí)現(xiàn)：KMP算法的思想:主串s,模式ｔ希望某趟在si和tj匹配失敗后，指針i不回溯，模式t向右“滑動(dòng)”至某個(gè)位置上,使得ｔk對(duì)準(zhǔn)si繼續(xù)向右進(jìn)行。顯然,現(xiàn)在問(wèn)題的關(guān)鍵是串t“滑動(dòng)”到哪個(gè)位置上？不妨設(shè)位置為k,即si和tｊ匹配失敗后，指針i不動(dòng),模式t向右“滑動(dòng)”，使tk和si對(duì)準(zhǔn)繼續(xù)向右進(jìn)行比較,要滿足這一假設(shè),就要有如下關(guān)系成立:"t1t２…tk-1"="ｓｉ-k＋1si-k+2…sｉ-1"(4.１）式左邊是tk前面的k-1個(gè)字符,右邊是ｓi前面的k-１個(gè)字符。而本趟匹配失敗是在sｉ和tj之處,已經(jīng)得到的部分匹配結(jié)果是:"ｔ1t2…tj-1"="ｓｉ-j+１ｓｉ-j+２…ｓｉ-1＂（４.2)因?yàn)椋?lt;j,所以有：＂tj－k＋１tj－k+２…tj-１＂=＂sｉ－k+1si-k+2…ｓｉ-1"（4.3)式左邊是tj前面的ｋ-1個(gè)字符,右邊是ｓi前面的ｋ－１個(gè)字符,通過(guò)（4.1)和(４.３)得到關(guān)系:＂t1t2…tｋ－1＂=＂tj-k+1tj-ｋ+2…ｔj－１＂(４.4)結(jié)論:某趟在sｉ和ｔj匹配失敗后,如果模式串中有滿足關(guān)系（４)的子串存在，即：模式中的前k-１個(gè)字符與模式中ｔj字符前面的ｋ-1個(gè)字符相等時(shí),模式ｔ就可以向右“滑動(dòng)”至使tk和sｉ對(duì)準(zhǔn)，繼續(xù)向右進(jìn)行比較即可。在求得模式的next函數(shù)之后，匹配可如下進(jìn)行:假設(shè)以指針i和ｊ分別指示主串和模式中的比較字符,令ｉ的初值為pｏs,j的初值為1。若在匹配過(guò)程中si≠tj,則ｉ和j分別增1,若si≠tj匹配失敗后,則i不變，j退到nｅxt[j]位置再比較，若相等,則指針各自增１，否則ｊ再退到下一個(gè)nexｔ值的位置，依此類推。直至下列兩種情況:一種是ｊ退到某個(gè)neｘｔ值時(shí)字符比較相等,則i和ｊ分別增１繼續(xù)進(jìn)行匹配;另一種是j退到值為零（即模式的第一個(gè)字符失配)，則此時(shí)i和j也要分別增1，表明從主串的下一個(gè)字符起和模式重新開(kāi)始匹配。ＫMP算法如下：intIndｅx＿KMP(SStrinｇS,SStringＴ，intpos，ｉntnext[］)｛//利用模式串Ｔ的ｎext函數(shù)求T在主串S中第ｐoｓ個(gè)字符之后的位置的/／KMP算法。其中，Ｔ非空。,１≤ｐos≤ＳtrLengtｈ(S）。i＝pｏs;ｊ=１;whiｌe(i<=S[０]&&j<=T[0])｛if(j==0｜｜s[i]==ｔ[j]){//繼續(xù)比較后繼字符++i;++j;｝ｅlsej=next[j］；//模式串向右移動(dòng)｝if(j>t［0］)retｕｒni-t[0];／/匹配成功ｅｌseｒｅturn0;}//Indeｘ_ＫMP４測(cè)試與分析４.1若匹配成功:調(diào)試結(jié)果如下圖所示圖4.1４.２若匹配不成功:調(diào)試結(jié)果如下所示圖4.25總結(jié)通過(guò)此次模式匹配中的KMP算法的實(shí)現(xiàn)的課設(shè)，我認(rèn)識(shí)到自己在以前的課程學(xué)習(xí)中還有很多的不足。在課設(shè)中，我了解到各種算法對(duì)軟件設(shè)計(jì)的重要性，它能幫助程序設(shè)計(jì)者設(shè)計(jì)出更好的程序?yàn)槿藗兊娜粘Ｉ钐峁┝烁蟮膸椭１敬握n設(shè)在平時(shí)的字符的查找中發(fā)揮了重要作用。這次課設(shè)讓我對(duì)Ｃ語(yǔ)言又復(fù)習(xí)了一遍。6附錄:源程序清單#inclｕde<stdio.h＞#ｉnclude<strｉnｇ.h>#iｎcluｄｅ<stdlib.ｈ>typeｄefstructLStｒing{ ／／串的鏈?zhǔn)酱鎯?chǔ)表示。?chａrdaｔａ; ｓtruｃtLStriｎg*ｎext;?｝LString;LString*Inpｕt(){?//通過(guò)標(biāo)準(zhǔn)輸入設(shè)備輸入串以鏈?zhǔn)酱鎯?chǔ)存儲(chǔ)數(shù)據(jù)并返回鏈的頭指針。?LStrinｇ*ｈead,*tａil，*p；intｃurlen＝０;chaｒｃh;head=(LSｔring＊)ｍallｏc(sizｅｏf（ＬStriｎg)）;／/建立頭指針。if（！head）{?pｒｉntf("存儲(chǔ)分配失敗")； exｉt(0);}//存儲(chǔ)分配失敗。ｓｃａｎf("%c"，&cｈ）;whｉle（ch!='\ｎ'）{p=(LＳtrｉng*)mａlloc(ｓizeof(LString));if（！p){printｆ("存儲(chǔ)分配失?。?;ｅxit(０)；}/／存儲(chǔ)分配失敗。p-＞ｄaｔａ＝ｃh；p－＞neｘt=NULＬ;iｆ(curｌeｎ==0)ｈead->next=p;eｌｓe{taｉl->nｅxt=ｐ;}tail＝p；++curlen;ｈead-＞ｄata=cｕrlｅn;//用頭指針存儲(chǔ)串的長(zhǎng)度sｃanf("%c",&ch);}returnhead;｝/／ＩｎputevoiｄOｕｔｐut(LStｒing*T){?／/在標(biāo)準(zhǔn)輸出設(shè)備上輸出串T。LStrinｇ*ｐ;p=T－>nｅxt;whｉle（p!=ＮUＬL){ｐrintf("%c",ｐ－＞data)；p=p－>nｅxt；}ｐrintf("\n"）;}／／OutputinｔLｅngｔh(LSｔrｉnｇ*T){ //求串T的長(zhǎng)度并返回其值。 intn=0;?LSｔrｉｎg＊hｅaｄ;?heaｄ=T；?if(head)n=hｅaｄ->ｄａt(yī)a;rｅturnn；}//LｅngthvｏidGｅt_nｅxt（LSｔring*T,ｉntneｘｔ[］){?/／求模式串T的ｎeｘt函數(shù)并存入數(shù)組next。ｉｎｔi＝1;intj＝0;intk;chaｒt[1０0];LString＊p;p=T;ｆoｒ(ｋ＝0;k<=Lｅnｇth(T)；k++)//將串T的鏈?zhǔn)酱鎯?chǔ)轉(zhuǎn)換為順序存儲(chǔ)并存入數(shù)組t。｛t［ｋ]＝p-＞datａ;p=p-＞next;}neｘt[1]=0;whiｌe(ｉ<ｔ[０］)｛if(j==0|｜t[i]=＝t[ｊ]){＋+i；++j;ｎｅxt[ｉ]=j;}elseｊ＝nexｔ[j];}ｎext[i+1］='\ｎ'；}／/Get_neｘtｉnｔIｎdeｘ＿KＭP(LString*S，ＬStriｎg*T,intpos,inｔｎexｔ[］){／/利用模式串T的nｅxt函數(shù)求T在主串S中第poｓ個(gè)字符之后的位置的/／KＭP算法。其中，T非空。,1≤pos≤ＳtｒLenｇｔh(S）。ｉｎti=ｐｏｓ;iｎtj=1;ｉntｋ;LSｔring*p,＊q;chars[255］,t[255];ｐ=S；q=T;for（k＝0；k＜=Leｎgth(Ｓ);k++)//將串S的鏈?zhǔn)酱鎯?chǔ)轉(zhuǎn)換為順序存儲(chǔ){s[k]＝p->ｄaｔa；p＝p-＞ｎexｔ；}ｆｏr(k=０；k<＝Leｎgth（T);ｋ++)//將串T的鏈?zhǔn)酱鎯?chǔ)轉(zhuǎn)換為順序存儲(chǔ){t[k]＝ｑ->ｄata;q＝ｑ->ｎｅxｔ;}ｗhiｌe（i＜=Lengtｈ（S)&&j<=Lengｔｈ（T)){iｆ（j==０||s[i]==t[j]){/／繼續(xù)比較后繼字符＋＋i;++j；}elsej=next[j］;//模式串向右移動(dòng)}ｉｆ(j＞t[0])ｒeｔurni－t[0];/／匹配成功elseretｕrn0;}//Index_KMPvoidmain(){sｙｓtem("cls＂)；system("cｏloｒ1f＂)；systeｍ（"ｍodecon:ｃｏlｓ=78lｉneｓ＝３5＂)；prｉntf（"┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");ｐrinｔｆ（＂┃㊣必做題4：KMP算法㊣┃\n")；pｒinｔf("┃姓名:ｘｘxｘ┃\ｎ");pｒｉntf（"┃學(xué)號(hào)：xxxxｘxxｘxx┃\ｎ");pｒintf（"┗━━━━━━━━━━━━━━━━━━━━━━━━━━━┛＼n＂);i