模式匹配的kmp算法(編輯修改稿)
2024-09-13 13:40 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 的取值為1。下面是利用上述規(guī)則求字符串P的失效函數(shù)值域的過(guò)程： 當(dāng)j=0時(shí)，由于0=k0,所以滿(mǎn)足條件的k并不存在，此時(shí)失效函數(shù)的取值為1，即f(0)=1.當(dāng)j=1時(shí)，k可能的取值為0，由于p0 ≠p1，所以k不能取0，此時(shí)滿(mǎn)足條件的失效函數(shù)的值仍為1，即f(1)=1。當(dāng)j=2時(shí)，k的可能取值為0,1。由于p0≠p2且p0p1 ≠p1p2，所以滿(mǎn)足條件的k不存在，即f(2)=1。當(dāng)j=3時(shí)，k可能的取值為0,1,2。由于p0≠p3，p0p1≠p2 p3且p0p1p2≠p1p2 p3。所以滿(mǎn)足條件的k不存在，即f(3)=1。當(dāng)j=4時(shí)，k可能的取值為0,1,2,3。由于p0=p4，p0p1≠p3 p4，p0p1 p2≠p2 p3 p4且p0p1 p2 p3≠p1p2 p3 p4。所以滿(mǎn)足條件的k為0，此時(shí)f(4)=0。當(dāng)j=5時(shí)，k可能的取值為0,1,2,3,4。由于p0≠p5，p0p1= p4p5，p0p1p2≠p3 p4 p5，p0p1 p2 p3≠p2 p3 p4 p5且p0p1 p2 p3 p4≠p1p2 p3 p4 p5，所以f(5)=1。同理可求當(dāng)j=6時(shí)，f(6)=1。求完模式串p的失效函數(shù)后，就可以應(yīng)用KMP算法對(duì)它進(jìn)行匹配。具體的匹配過(guò)程分為兩種情況。假設(shè)在進(jìn)行某一輪比較時(shí)，失配的情況發(fā)生在模式p的第j位，那么如果j=0，則讓目標(biāo)的指針前進(jìn)一位，模式串的起始比較地址 回到P0處。否則，在進(jìn)行下一輪的比較時(shí)，目標(biāo)指針不發(fā)生回溯，仍指向失配的位置，而模式串的起始比較地址為Pf(j1)+，函數(shù)f(j)僅與字符串P有關(guān)，而與目標(biāo)串無(wú)關(guān)。所以只需給定
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1