用一個實(shí)際的例子來說明，經(jīng)歷了看懂，看不懂，看懂，看不懂，看懂...后我終于決定把它記下來了。

例子字符串為：abaabaca

首先可以肯定，第一個位置永遠(yuǎn)位0，第二個位置永遠(yuǎn)為1.那么可以初始化如下表格：

a	b	a	a	b	a	c	a
0	1	?	?	?	?	?	?

然后求上表中紅色的a多對應(yīng)的值:公式為（a前面的字符串中所有前綴字符與a前面的字符串中所有后綴自付中所有后綴字符相同的字符的最大中長度最長的長度）+1；

公式看起來很復(fù)雜，一步一步來說明：

首先是前綴字符和后綴字符，拿字符abcde來舉例：

前綴字符有：a、ab、abc、abcd ；后綴字符有：e、de、cde、bcde；

由此可見前綴字符就是第一個字符、（第一個字符第二個字符）、... 、（第一個字符...第n-1個字符）

? ? ? ? ? ? ? ?后綴字符就是第n個字符、（第n-1個字符第n個字符）、... 、 （第二個字符...第n個字符）

在abcde中，前綴字符與后綴字符沒有相同的字符串存在，所以最大的相同字符串的長度位0；

在回到上表中的紅色的a，它前面的字符串為? ab? ；ab的前綴字符有 ｛a｝ ；后綴字符有｛b｝，最大的相同字符串的長度為0，

根據(jù)公式，上表中紅色的a對應(yīng)的位置應(yīng)當(dāng)填入0+1=1；獲得下表：

a	b	a	a	b	a	c	a
0	1	1	?	?	?	?	?

下面求上表中紅色a位置的值

?上表中紅色a前面的字符串為 aba； 它的前綴字符串有 ｛a ,ab｝;后綴字符串有｛a,ba｝;最大的相同字符串的長度為1（都有相同的元素a），根據(jù)公式，上表中紅色的a對應(yīng)的位置應(yīng)當(dāng)填入1+1=2；獲得下表：

a	b	a	a	b	a	c	a
0	1	1	2	?	?	?	?

然后求上表中紅色b位置的值

上表中紅色b前面的字符串為 abaa；它的前綴字符串有｛a , ab,aba｝;后綴字符串有｛a,aa,baa｝;最大的相同字符串的長度為1（都有相同的元素a），根據(jù)公式，上表中紅色的b對應(yīng)的位置應(yīng)當(dāng)填入1+1=2；獲得下表：

a	b	a	a	b	a	c	a
0	1	1	2	2	?	?	?

然后求上表中紅色a位置的值

上表中紅色a前面的字符串為 abaab;它的前綴字符串有｛a,ab,aba,abaa｝;后綴字符串有{b,ab,aab,baab};最大的相同字符串的長度為2（都有相同的元素ab），根據(jù)公式，上表中紅色a對應(yīng)的位置應(yīng)當(dāng)填入2+1=3；獲得下表：

a	b	a	a	b	a	c	a
0	1	1	2	2	3	?	?

然后求上表中紅色c位置的值

上表中紅色c前面的字符串為abaaba;它的前綴字符串有｛a,ab,aba,abaa,abaab｝;后綴字符串有｛a,ba,aba,aaba,baaba｝;最大的相同字符串的長度為3（都用相同的元素aba），根據(jù)公式，上表中紅色a對應(yīng)的位置應(yīng)當(dāng)填入3+1=4；獲得下表：

a	b	a	a	b	a	c	a
0	1	1	2	2	3	4	?

最后就是求上表中紅色的a的值了，自己試試吧，答案選中下面的表格得見：

a	b	a	a	b	a	c	a
0	1	1	2	2	3	4	1

總結(jié)

以上是生活随笔為你收集整理的KMP算法NEXT数组纯手工生成的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。