本文是介紹 什麼是 BF算法、KMP算法、BM算法 三部曲之一。
KMP算法 內部涉及到的數學原理與知識太多,本文只會對 KMP算法 的運行過程、 部分匹配表 、next數組 進行介紹,如果理解了這三點再去閱讀其它有關 KMP算法 的文章肯定能有個清晰的認識。
以下的文字描述請結合視頻動畫來閱讀~
定義
Knuth-Morris-Pratt 字符串查找算法,簡稱為 KMP算法,常用於在一個文本串 S 內查找一個模式串 P 的出現位置。
這個算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人於 1977 年聯合發表,故取這 3 人的姓氏命名此算法。
是不是感覺 Donald Knuth 這個名字很眼熟?沒錯,在前面 這或許是講解 Knuth 洗牌算法最好的文章 一文中也出現了他!
KMP算法 的操作流程如下:
- 假設現在文本串 S 匹配到 i 位置,模式串 P 匹配到 j 位置
- 如果 j = -1,或者當前字符匹配成功(即 S[i] == P[j] ),都令 i++,j++,繼續匹配下一個字符;
如果 j != -1,且當前字符匹配失敗(即 S[i] != P[j] ),則令 i 不變,j = next[j]。此舉意味著失配時,模式串 P相對於文本串 S 向右移動了 j - next [j] 位 - 換言之,將模式串 P 失配位置的 next 數組的值對應的模式串 P 的索引位置移動到失配處
運行過程
以下圖文本串 S 與模式串 P 為例:
首先,列出模式串 P 的所有子串:
a | ||||||||
---|---|---|---|---|---|---|---|---|
a | b | |||||||
a | b | a | ||||||
a | b | a | a | |||||
a | b | a | a | b | ||||
a | b | a | a | b | c | |||
a | b | a | a | b | c | a | ||
a | b | a | a | b | c | a | c |
然後,求得每一個子串的所有前綴與後綴。
前綴 指除了最後一個字符以外,一個字符串的全部頭部組合;後綴 指除了第一個字符以外,一個字符串的全部尾部組合。
以第五列為例進行演示。
前綴為
a | ||||
---|---|---|---|---|
a | b | |||
a | b | a | ||
a | b | a | a |
後綴為
b | ||||
---|---|---|---|---|
a | b | |||
a | a | b | ||
b | a | a | b |
因此,它的前綴後綴的公共元素的最大長度為 2。
求得原模式串 P 的子串對應的各個前綴後綴的公共元素的 最大長度表 下圖。
根據最大長度表 去求 next 數組:next 數組相當於“最大長度值” 整體向右移動一位,然後初始值賦為-1。
好了,獲取了 next 數組 後,KMP 算法 的操作就很清晰了。
將模式串 P 與文本串 S 的字母一個個進行匹配,當失配的時候,模式串向右移動。
怎麼移動?
比如模式串的 b 與文本串的 c 失配了,找出失配處模式串的 next數組 裡面對應的值,這裡為 0,然後將索引為 0 的位置移動到失配處。
後記
市面上好多講解 KMP算法 的文章的寫的太混亂了,很多人因此產生了恐懼,這一章目的就是為了能讓大家能大概理解 KMP算法 的運行過程,不會畏懼 KMP算法 。
來源 | 五分鐘學算法
作者 | 程序員小吳