kmp算法課件演示(推薦)

《kmp算法課件演示(推薦)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、kmp算法課件演示(推薦)數(shù)據(jù)結(jié)構(gòu)/數(shù)據(jù)庫2007-10-1222:23:51閱讀625評論1??字號：大中小?訂閱(1)以一個例子引入KMP算法先看樸素模式匹配過程：(a)S：abbaba==≠P：aba012(b)P3≠S3,P右移一位S：abbaba(c)P1≠S2,P右移一位S：abbaba≠P：aba(d)P1≠S3,P右移一位S：abbaba===P：aba(e)匹配成功index(S,P)=4,substr(S,4,3)=P??從匹配過程看：首先在(a)中p1=s1,p2=s2,p3≠s3,只需將

2、模式右移到s3，不需將主串回溯到s2；其次，由于p1≠p2，可推出p1≠s2,做(b)的比較一定不等；?再由p1=p3,可以推出p1≠s3，做(c)的比較也一定不等。因此，由(a)便可直接將P右移三位跳到(d)，從p1和t4開始進行比較，這樣的匹配過程對S(主串)而言就消除了回溯。為要找到一個無回溯的匹配算法，關(guān)鍵在于當匹配過程中，一旦pj和si比較不等，存在:?substr(p,1,j-1)=substr(s,i-j+1,j-1)pj≠si?改進的模式匹配算法的思想：在匹配過程中，當主串第i個字符與模式串第j

3、個字符“失配”時，要產(chǎn)生模式串右移的位數(shù)和繼續(xù)與主串（主串無回溯的）比較的字符，即應(yīng)該用P中哪個字符和Si進行比較？把這個字符記為Pk，顯然有k

4、j+1…..pm假設(shè)此時應(yīng)與模式串中第k個字符繼續(xù)比較，則模式中前k-1個字符的子串必須滿足下列關(guān)系：“p1p2…pk-1”=“si-k+1si-k+2…si-1”由部分匹配知：“pj-k+1pj-k+2…pj-1”=“si-k+1si-k+2…si-1”推得：“p1p2…pk-1”=“pj-k+1pj-k+2…pj-1?????????????????0當j=1時?next[j]=?Max{k

5、1

6、c01112?例：ˉi=3第一趟匹配ababcabcacbababcacj=3next[3]=1ˉi—?ˉi=7第二趟匹配ababcabcacbababcac—?j=5next[5]=2j=1ˉi—?ˉi=10第三趟匹配ababcabcacbababcacj=2?其意義在于：若next[j]>0表示一旦匹配過程中Pi與Si比較不等，可用模式中next[j]為下標的字符與Si進行比較；若next[j]=0表示P中任何字符都不必再與Si進行比較，而從Si+1開始。對于任何模式P，主要的是要確定next[j](j=1

7、,2,3…m)值，next[j]確定了，就可以加快匹配的過程。當Pj≠Si時，P直接右移j-next[j]個字符，或者說P從next[j]開始與Si繼續(xù)比較下去。?KMP算法：假設(shè)next[j]已經(jīng)生成。intindex_KMP(strtypep,strtypes,intpos){inti=pos,j=1;while(j<=m&&i<=n)//m是模式串p的串長，n是主串s的串長{if(j==0

8、

9、s.str[i]==p.str[j]);{i++;j++;}elsej=next[j];}if(j>m)retur

10、ni-m;elsereturn0;}?(2)next[j]數(shù)組的性質(zhì)從上面的分析可以看出，此種算法的關(guān)鍵在于確定next[j]數(shù)組。若令next[j]=k,則有：?①?1≤k

11、的生成由性質(zhì)可知，next[j]的值就等于這個串p1p2pj-1中相同的前綴子串和后綴子串的最大長度加1。找前綴和后綴相同的最大真子串，實質(zhì)上仍然是一個模式匹配，只是匹配的模式串和目標串是同一個串P。由定義知：a.next[1]=0設(shè)next[j]=kb.若pk=pj時，則next[j+1]=next[j]+1c.若pk≠pj，則next[j+1]=next[k]+1d.若不存在匹配的