天天看點

KMP算法

在文本中找到模式字元串首次出現的位置。

文本:String text

模式字元串:String pattern

1、字首:表示包含首位字元但不包含末位字元的子串

2、字尾:表示包含末位字元但不包含首位字元的子串

3、next數組

next[i]:表示模式字元串的子串 pattern[0,1,……, i] 中,前字尾相等的長度有多長。

KMP算法

如上圖所示,text="ABCDABEABCDABD",pattern="ABCDABD"。當比較到 i = 6,j = 6的時候,發現不比對。此時對應的代碼是

目前 j = 6,則 執行語句 j = next[j-1],j 的值更新為2。将 text[6]與pattern[2] 比較,發現還是不相等。繼續循環。

目前 j = 2,則 執行語句 j = next[j-1],j 的值更新為0。将 text[6]與pattern[2] 比較,發現還是不相等。因為循環條件 j>0 不成立,結束循環。目前 i = 6, j = 0。執行以下代碼。

将 text[6]與pattern[2] 比較,發現不相等,是以第一個 if 語句不成立。

目前 j = 0 ,第二個 if 語句也不成立。目前循環結束,i++。目前 i = 7,j = 0。

KMP算法

1、 幫你把KMP算法學個通透

2、 很詳盡的KMP算法