KMP算法講解之——不需要公式,就能理解KMP算法.ppt

《KMP算法講解之——不需要公式,就能理解KMP算法.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、KMP算法20XX.XX.XX匯報(bào)人：XXX匯報(bào)提綱KMP算法一.KMP背景介紹三.KMP核心——跳轉(zhuǎn)表next[]二.由樸素匹配到KMP四.next[]的計(jì)算——引入f(j)KMP算法一.KMP背景介紹在文本編輯中，我們經(jīng)常要在一段文本中某個(gè)特定的位置找出某個(gè)特定的字符或模式。再比如，在HTTP協(xié)議里的字節(jié)流,有各種關(guān)鍵的字節(jié)流字段,對(duì)HTTP數(shù)據(jù)進(jìn)行解釋就需要用到模式匹配算法。由此，便產(chǎn)生了字符串的匹配問(wèn)題。KMP算法是由Knuth，Morris，Pratt三人共同提出的模式匹配算法，其對(duì)于任何模式和目標(biāo)序列，都可以在線性時(shí)間內(nèi)完成匹配查找，而不會(huì)發(fā)生退化，是一個(gè)非常優(yōu)秀的模式匹配算

2、法。KMP算法二.由樸素匹配到KMP假設(shè)有目標(biāo)字符串(Target)T=babcbabcabcaabcabcabcacabc，我們要在其中找到模式字符串（Pattern）P=abcabcacab。如何做更為高效呢？由樸素匹配，我們要做16次，而KMP算法僅匹配了6次就找到了模式字符串樸素匹配的時(shí)間復(fù)雜度為O(m*n)；KMP的時(shí)間復(fù)雜度為O(n)。KMP算法三.KMP算法核心——跳轉(zhuǎn)表next[]其實(shí)，模式串往往含有一定的信息——前綴包含。對(duì)于模式串而言，其前綴字符串，有可能也是模式串中的非前綴子串，這個(gè)問(wèn)題我稱之為前綴包含問(wèn)題。那么每次要跳躍多少呢？這與跳轉(zhuǎn)表next[]存儲(chǔ)的數(shù)值相關(guān)

3、。以模式串a(chǎn)bcabcacab為例，其前綴的4個(gè)字符abca，正好也是模式串的一個(gè)子串a(chǎn)bc(abca)cab，所以當(dāng)目標(biāo)串與模式串執(zhí)行匹配的過(guò)程中，如果直到第8個(gè)字符才匹配失敗，同時(shí)也意味著目標(biāo)串當(dāng)前字符之前的4個(gè)字符，與模式串的前4個(gè)字符是相同的，所以當(dāng)模式串向后移動(dòng)的時(shí)候，可以直接將模式串的第5個(gè)字符與當(dāng)前字符對(duì)齊，執(zhí)行比較，這樣就實(shí)現(xiàn)了模式串一次性向前跳躍多個(gè)字符。KMP算法三.KMP算法核心——跳轉(zhuǎn)表next[]模式字符串P=abcabcacab，其跳轉(zhuǎn)表為：KMP算法三.KMP算法核心——跳轉(zhuǎn)表next[]我們以KMP匹配的第3步為例:此時(shí)pattern串的第1個(gè)字母與tar

4、get[6]對(duì)齊，從6向后依次匹配目標(biāo)串，到target[13]時(shí)發(fā)現(xiàn)target[13]='a'，而pattern[8]='c'，匹配失敗，此時(shí)next[8]=5，所以將模式串向后移動(dòng)8-next[8]=3個(gè)字符，將pattern[5]與target[13]對(duì)齊，然后由target[13]依次向后執(zhí)行匹配操作。在整個(gè)匹配過(guò)程中，無(wú)論模式串如何向后滑動(dòng)，目標(biāo)串的輸入字符都不會(huì)回溯，直到找到模式串，或者遍歷整個(gè)目標(biāo)串都沒(méi)有發(fā)現(xiàn)匹配模式為止。KMP算法四.next[]的計(jì)算——引入f(j)跳轉(zhuǎn)表next[]是如何計(jì)算的呢？以及怎樣以較小的代價(jià)計(jì)算?這里我們引入一個(gè)概念f(j)，其含義是，對(duì)于

5、模式串的第j個(gè)字符pattern[j]，f(j)是所有滿足使pattern[1···k-1]=pattern[j-(k-1)···j-1](k

6、abcdababg，則f(11)=5!=3。如何理解取K最大值呢？通過(guò)上圖，我們不難看出，k越小，跳躍的步伐越大，很可能會(huì)把滿足條件的匹配結(jié)果跳過(guò)去，因此我們?cè)诒ＷC算法快速的同時(shí)，還要保證準(zhǔn)確！KMP算法四.next[]的計(jì)算——引入f(j)為了說(shuō)明f(j)和next[j]之間的關(guān)系，我們以pattern[8]為例，假如匹配到pattern[8]才匹配失敗。f(8)=5,pattern[1···4]=pattern[4···7]，此時(shí)我們需要關(guān)注pattern[8]：1.如果pattern[8]!=pattern[5]因?yàn)樵谄ヅ涞絧attern[8]時(shí)才失敗，此時(shí)就可以將輸入字符targ

7、et[n]與pattern[f(8)]=pattern[5]對(duì)齊，再向后依次執(zhí)行匹配，所以此時(shí)的next[8]=f(8)。KMP算法四.next[]的計(jì)算——引入f(j)2.如果pattern[8]=pattern[5]那么pattern[1···5]=pattern[4···8]，因?yàn)閠arget[n]與pattern[8]匹配失敗，那么也意味著target[n-4···n]!=pattern[4···8]，那么將target[n