next數組演算法

A. KMP 演算法中 next 數組手工求解

KMP演算法是一種改進的字元串匹配演算法，如果不研究編碼的話，手工實現還是比較簡單，小型字元串甚至不需要你去求 next 數組就能看出來怎麼移動。但是會有一些題目讓你求解 next 數組，這里就以一個題目講一下手工求解的過程。

例：求串 『ababaaababaa』 的 next 數組

觀察第一個元素，它沒有前綴和後綴（串本身不能作為前綴或後綴），所以記錄數據為0（這個數字表示當存在前綴和後綴相同的情況下，所能包含的最大的元素）

觀察前兩個元素，前綴為a，後綴為b，不相同，即沒有相同的前綴和後綴，所以同樣記錄數據為0

觀察前三個元素，存在前後綴相同的情況，為a，記錄數據為1

觀察前四個元素，同樣存在前綴後綴相同的情況，為ab，記錄數據為2

觀察第五個元素，相同的前後綴為aba（ aba ba、ab aba ），記錄數據為3

同理觀察餘下的（用加粗表示前綴、下劃線表示後綴）

a baba_a_ 1

a babaa_a_ 1

ab abaa_ab_ 2

aba baa_aba_ 3

abab aa_abab_ 4

ababa a_ababa_ 5

ababaa ababaa 6

最後我們得到一組數值：0 0 1 2 3 1 1 2 3 4 5 6

在這組數開頭添加 -1，並刪去最後一個數值，數組變為： -1 0 0 1 2 3 1 1 2 3 1 1 2 3 4 5

所有值+1，變為：0 1 1 2 3 4 2 2 3 4 2 2 3 4 5 6，這就是我們需要的 next 數組

需要注意的是，不同的題目next[0]可能為-1，所以 -1 0 0 1 2 3 1 1 2 3 1 1 2 3 4 5 同樣有可能作為 next 數組，但是這兩種一定不會同時出現。

題目圖片：

B. kmp演算法中的next到底是什麼意思啊

next[j]表代表j之前的字元串的真前綴和真後綴最大匹配長度，它的構成和kmp演算法思想一致，只需要置next[0]=-1，再逐次推出next[j]的值

C. 模式匹配KMP演算法裡面next里保存的值有什麼用

next數組存儲的數據是用來當模式串與主串不匹配的時候要模式串回退到第幾個字元與主串再重新匹配，我們知道KMP演算法的主串是不回朔的，當不匹配的時候我們不是退回到開始位置重新匹配，而是利用已經匹配的結果將模式串回朔到下一個位置，這個位置比開始位置更近一步;
簡單的說就是next[ j ]的值保存的是當模式串中第 j 個字元與主串第 i 個字元不匹配時候，模式串中的哪個字元 重新與主串第 i 個再匹配，這樣總的字元比較次數比從開始位置比較的次數就少了。