當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

KMP算法中NEXT数组的作用以及代码实现

發布時間：2025/3/15 编程问答 18 豆豆

生活随笔收集整理的這篇文章主要介紹了 KMP算法中NEXT数组的作用以及代码实现小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

在http://blog.csdn.net/u012613903/article/details/79004094中寫到了如何手工去求一個NEXT數組，這個在很多考試中可以用來解題。但是在實際的使用中，NEXT數組究竟發揮著什么樣的作用，如何用代碼實現KMP算法呢？

KMP算法是用來確定一個串是否能在另一個串中找到與之完全匹配的子串，那么首先來看一個字符串匹配的實際例子；

被匹配的字符串：

要匹配的字符串：

下面開始進行匹配：（i代表被匹配的字符串的當前字符下標；j代表要匹配的字符串的當前字符下標。）

0	1	2	3	4	5	i	?
a	b	c	d	a	b	e	f
a	b	c	d	a	b	w	?
0	1	2	3	4	5	j	?

可以看到，在{e,w}的位置匹配失敗了，如果使用暴力的方法做，那么下一次的匹配就變成了這個樣子：

0	i	2	3	4	5	6	7
a	b	c	d	a	b	e	f
?	a	b	c	d	a	b	w
?	j	1	2	3	4	5	6

這時候 i = i-j+1；j=0；這就是暴力算法的思想：一旦匹配失敗，就讓要匹配的字符串從頭開始與被匹配的字符串進行匹配。

我們來觀察第一次匹配失敗后的情況：

0	1	2	3	4	5	i	?
a	b	c	d	a	b	e	f
a	b	c	d	a	b	w	?
0	1	2	3	4	5	j	?

在要匹配的字符串的｛w｝位置，往前看，看到?的a，b與實心?的a，b就是我們要求的最長的相同前綴與后綴字符串

其實它們代表的實際意義是這樣的：

在｛e，w｝位置無法進行匹配了，但是在w之前的要匹配的字符串的所有字符都與在e之前的被匹配的字符串的所有字符完全匹配了；（這是個前提標記為@1）

下面具體分析實際情況：

a	b	c	d	a	b	e	f
a	b	c	d	a	b	w	?

在｛e，w｝位置匹配失敗了，我們不想使用暴力方法；想省力，那該怎么辦呢？

要匹配的串中的w和被匹配串的e不匹配，進行下次匹配的時候，必然會有要匹配串中的w之前的某個字符取代w。也就是要將要匹配的串向右平移一個量(j+這個量<=i)。這里我們列出所有的平移情況：

(1)

(2)

(3)

(4)

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

(5)

? ?

(6)

上面就是所有的平移情況，情況（1），（2），（3）從第一個就不匹配；情況（4）從第三個不匹配；（5），（6）不需要討論；可以看到，在（4）之前都是從第一個字符起兩個串就不匹配，直到（4）才出現不是在第一個字符就不匹配的情況。然后再看（4）中的匹配上的字符串，居然是 a，b，是要匹配的最長的相同前綴與后綴字符串。為什么會這樣，這就用到了上面的前提@1 。

再回到最初不匹配的情形下：

a	b	c	d	a	b	e	f
a	b	c	d	a	b	w	?

正如前提@1所說，e，w之前兩個字符串完全匹配，也就是完全相同。所以要求被匹配串e之前與要匹配串從0開始相同的最長子串串也就變成了在要匹配字串中求w之前與要匹配串中從0開始相同的最長子串

a	b	c	d	a	b	e	f
a	b	c	d	a	b	w	?

就像圖中表示的那樣，要求黃色與紅色的關系，就是求綠色與紅色的關系；所以我們在求NEXT數組時所求出的最長的相同前綴與后綴字符串就是在不匹配的位置之前被匹配字符串中與要匹配的字符串中從0開始所以字符完全相同的最長的子串。

然后(1)->(2)->(3)->(4)的平移過程，其實就是使用暴力法的過程；KMP算法就是利用了這個特性，在某個位置發生不匹配的情況后，直接將比較情況變成（4）跳過了（1）、（2）、（3）這些從一開始就不匹配的匹配情況，而且斷定了在a，b已經匹配，只需要測試a，b之后的字符是否匹配就可以了，如下圖所示：

在i的位置發生了不匹配，直接平移到了上圖中的情況，然后直接從j=2位置的要匹配字符串的字符與i=6位置的被匹配字符串的字符進行對比就可以了；

為什么能跳過暴力算法的從開始就不匹配的步驟，并且確定了這次比較中已經匹配的字符串的長度呢？

個人理解：在i位置發生了不匹配的情況，我們從i往前逐漸加大長度來取得字符串，然后確定這個字符串在要匹配的串中從0開始能否得到，知道走到得不到的時候，

也就是恰好如上圖中的 a,b,c中的c與 d,a,b中的b不想同的時候，由于d的出現，就可以確定它們從一開始就無法匹配；而反之取到 a，b的時候，說明a，b是可以匹配的，只需要確定i以及i之后與a，b之后是否能夠匹配就可以了。

最后確定一下j與NEXT數組的關系，求出要匹配的字符串的NEXT數組的值，如下：

a	b	c	d	a	b	w
0	1	1	1	1	2	3

在這里，j=NEXT值-1；其中當NEXT為0的時候，j=-1；這種情況說明第一個字符就不匹配，在算法中i會直接+1，然后j也直接+1；也就是從被匹配串的第i+1位置和要匹配串從0開始進行匹配。

下面是算法的具體實現，（最近在學python，所以就用python寫了；PS：求next數組不是最優化的算法）

# -*- coding:utf-8 -*- # Author: Evan Midef kmp(haystack, needle):slen = len(haystack)plen = len(needle)nexts = [0] * plenget_next(needle, nexts)print(nexts)i = 0j = 0 """ 當haystack[i] == needle[j]的時候，直接i++，j++看下一個是否匹配一旦不匹配那么i不變，j=nexts[j]-1；邊界情況下，j=nexts[0]-1=-1; 這中情況說明沒有滿足的NEXT值，也就是在i前面的已匹配字符串的長度為-1 也就是在i+1前面已匹配的字符串的長度為0（即從i+1與j=0處開始比較），恰好也對應i++ （=>i+1），j++( =>0)然后看下一個是否匹配 """while i < slen and j < plen:if haystack[i] == needle[j] or j == -1:i += 1j += 1else:j = nexts[j]-1if j == plen:return i-jelse:return -1""" 設要求的字符串為A 在求next數組的時候我們已經求的了位置j的NEXT值為k+1 也就是說在要求的字符串中從[0到k-1]與[j-k到j-1]完全相同，所以如果A[k]=A[j]的時候，只需要j++；k++；nexts[j]=k+1 就求的了j+1位置的NEXT值當A[k]!=A[j]的時候，我們把A進行復制，賦值一個A'；讓k對應與A',讓j對應于A；且容易得到A'的NEXT數組和A完全相同就可以看作在A'中[0,k-1]與A中[j-k,j-1]完全相同（也就是匹配成功），但是在{j,k}處匹配失敗，所以j不變，而是將 k賦值為next[k]-1（在k之前的所有NEXT值是已經求得的），最差的情況k會取到NEXT[0]-1也就是k=-1；這時在j+1之前的A' 的長度是k+1=0；所以A[j+1]要與A'[0]對應，也就是k=0；所以也需要執行操作j++ ( =>j+1),k++( =>0) 然后nexts[j]=k+1 """def get_next(needle, nexts):al = len(needle) #求出要求NEXT數組的字符串的長度nexts[0] = 0 #NEXT[0]是恒定值0k = -1j = 0while j < al - 1: if k == -1 or needle[j] == needle[k]:j += 1k += 1nexts[j] = k+1else:k = nexts[k]-1print(kmp("hello", "ll"))

總結

以上是生活随笔為你收集整理的KMP算法中NEXT数组的作用以及代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。