KMP演算法之所以叫做KMP演算法是因為這個演算法是由三個人共同提出來的，就取三個人名字的首字母作為該演算法的名字。其實KMP演算法與BF演算法的區別就在於KMP演算法巧妙的消除了指標i的回溯問題，只需確定下次匹配j的位置即可，使得問題的複雜度由O(mn)下降到O(m+n)。 在KMP演算法中，為了確定在匹配不成功時，下次匹配時j的位置，引入了next[]陣列，next[j]的值表示P[0...j-1]中最長字尾的長度等於相同字元序列的字首。 對於next[]陣列的定義如下： 1) next[j] = -1 j = 0 2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k,j-1] 3) next[j] = 0 其他 如： P a b a b a j 0 1 2 3 4 next -1 0 0 1 2 即next[j]=k>0時，表示P[0...k-1]=P[j-k,j-1] 因此KMP演算法的思想就是：在匹配過程稱，若發生不匹配的情況，如果next[j]>=0，則目標串的指標i不變，將模式串的指標j移動到next[j]的位置繼續進行匹配；若next[j]=-1，則將i右移1位，並將j置0，繼續進行比較。
KMP演算法之所以叫做KMP演算法是因為這個演算法是由三個人共同提出來的，就取三個人名字的首字母作為該演算法的名字。其實KMP演算法與BF演算法的區別就在於KMP演算法巧妙的消除了指標i的回溯問題，只需確定下次匹配j的位置即可，使得問題的複雜度由O(mn)下降到O(m+n)。 在KMP演算法中，為了確定在匹配不成功時，下次匹配時j的位置，引入了next[]陣列，next[j]的值表示P[0...j-1]中最長字尾的長度等於相同字元序列的字首。 對於next[]陣列的定義如下： 1) next[j] = -1 j = 0 2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k,j-1] 3) next[j] = 0 其他 如： P a b a b a j 0 1 2 3 4 next -1 0 0 1 2 即next[j]=k>0時，表示P[0...k-1]=P[j-k,j-1] 因此KMP演算法的思想就是：在匹配過程稱，若發生不匹配的情況，如果next[j]>=0，則目標串的指標i不變，將模式串的指標j移動到next[j]的位置繼續進行匹配；若next[j]=-1，則將i右移1位，並將j置0，繼續進行比較。