kmp演算法next數組
1. kmp演算法中的next到底是什麼意思啊
next[j]表代表j之前的字元串的真前綴和真後綴最大匹配長度，它的構成和kmp演算法思想一致，只需要置next[0]=-1，再逐次推出next[j]的值
2. 給出字元串在KMP演算法中的Next數組
逐個查找對稱串。
只要循環遍歷這個子串，分別看前1個字元，前2個字元，3個... i個 最後到15個。
第1個a無對稱，所以對稱程度0
前兩個ag無對稱，所以也是0
依次類推前面0-4都一樣是0
最後一個是0～3都一樣是0
前綴next數組的求解演算法：
void SetPrefix(const char *Pattern, int prefix[])
{
int len=CharLen(Pattern);//模式字元串長度。
prefix[0]=0;
for(int i=1; i<len; i++)
{
int k=prefix[i-1];
//不斷遞歸判斷是否存在子對稱，k=0說明不再有子對稱，Pattern[i] != Pattern[k]說明雖然對稱，但是對稱後面的值和當前的字元值不相等，所以繼續遞推
while( Pattern[i] != Pattern[k] && k!=0 )
k=prefix[k-1]; //繼續遞歸
if( Pattern[i] == Pattern[k])//找到了這個子對稱，或者是直接繼承了前面的對稱性，這兩種都在前面的基礎上++
prefix[i]=k+1;
else
prefix[i]=0; //如果遍歷了所有子對稱都無效，說明這個新字元不具有對稱性，清0
}
}
(2)kmp演算法next數組擴展閱讀：
設主串（下文中我們稱作T）為：a b a c a a b a c a b a c a b a a b b
模式串（下文中我們稱作W）為：a b a c a b
用暴力演算法匹配字元串過程中，我們會把T[0] 跟 W[0] 匹配，如果相同則匹配下一個字元，直到出現不相同的情況，此時會丟棄前面的匹配信息，然後把T[1] 跟 W[0]匹配，循環進行，直到主串結束，或者出現匹配成功的情況。這種丟棄前面的匹配信息的方法，極大地降低了匹配效率。
而在KMP演算法中，對於每一個模式串我們會事先計算出模式串的內部匹配信息，在匹配失敗時最大的移動模式串，以減少匹配次數。
3. KMP演算法的next數組默認要不要+1啊
KMP演算法，主要分為2個階段：
求next數組。
字元串匹配
next數組，就是對給定的「匹配字元串」，求出其每一個子長度字串的「最長前綴和最長後綴相等的長度」。
匹配串，p="aabcaabbaa", 長度n=10。因此子串為sub[10]：
sub[0] = "a"
sub[1] = "aa"
sub[2] = "aab"
sub[3] = "aabc"
sub[4] = "aabca"
sub[5] = "aabcaa"
sub[6] = "aabcaab"
sub[7] = "aabcaabb"
sub[8] = "aabcaabba"
sub[9] = "aabcaabbaa"
根據「最長前綴和最長後綴相等的長度」，可以求出對應的next數組是：
next[0] = -1; // "a"
next[1] = 0; // "aa"
next[2] = -1; // "aab"
next[3] = -1; // "aabc"
next[4] = 0; // "aabca"
next[5] = 1; // "aabcaa"
next[6] = -1; // "aabcaab"
next[7] = -1; // "aabcaabb"
next[8] = 0; // "aabcaabba"
next[9] = 1; // "aabcaabbaa"
2. 利用上部求出的next數組，對t和p進行匹配。要點是：
（1）循環匹配
（2）如果整個匹配上，則返回匹配位置。
（3）如果當前位置沒有匹配上，則：如果對應next[x]為-1，則跳過整個p的長度；否則，回溯到其前綴位置進行匹配。匹配上，則右移next[x-1]位置；否則，右移next[x]位置。
具體到「多少次字元匹配」，在編制的程序里加上統計的語句，最後輸出。真要一個個字元統計，很容易出錯。
4. 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 數組，但是這兩種一定不會同時出現。
題目圖片：
5. KMP演算法中的next數組如何計算
一個串的next數組，可以這樣理解
對於next[i]的值，等於該串0~i-1的這個串中，前幾個字元組成的串，與後幾個字元完全相同。
舉個例吧，ababc，next數組下標就是0~4的范圍啦~~
首先next[0]=0，這是肯定的，其實next[0]沒意義。。。
計算next[1]，先看原串該位置之前的子串，即a，從前往後數1，與從後往前數1，串都是a，相等，故next[1]=1
然後next[2]，前綴串為ab，從前往後數1，與從後往前數1，子串分別為a,b，不等，所以next[2]=0
next[3]，對於前綴串aba，從前往後數1，與從後往前數1，串都是a相等。但是，數到2時，ab與ba不等，故next[3]=1
對於next[4]，前綴串abab，雖然去長度1時，子串不等。但數到2時，子串均為ab，相等。故next[4]=2
以此類推，就是數前綴串中，前數幾個與後數幾個，取到子串相等時，最大數到幾。當然，這樣數不能數到盡頭。。。
6. 數據結構與演算法——字元串匹配問題(KMP演算法)
KMP演算法也是比較著名的模式匹配演算法。是由 D.E.Knuth,J.H.Morrs 和 VR.Pratt 發表的一個模式匹配演算法。可以大大避免重復遍歷的情況。
如果使用暴風演算法的話，前面五個字母完全相等，直到第六個字母 "f" 和 "x" 不相等。如下圖：
T = 「abcdex」
j 123456
模式串 abcdex
next[j] 011111
T = "abcabx"
j 123456
模式串T abcabx
next[j] 011123
T = "ababaaaba"
j———————123456789
模式串T——— ababaaaba
next[j]————011234223
T = "aaaaaaaab"
j———————123456789
模式串T——— aaaaaaaab
next[j]————012345678
next數組其實就是求解字元串要回溯的位置
假設，主串S= 「abcababca」;模式串T=「abcdex」，由以上分析得出next數組為011111，next數組意味著當主串與模式串不匹配時，都需要從第一個的位置重新比較。
KMP演算法也是有缺陷的，比如主串S=「aaaabcde」,模式串T= 「aaaaax」。next的數組就是012345；
當開始匹配時，當i= 5，j = 5時，我們發現字元"b"與字元「a」不相等，如上圖，j = next[5] = 4;
由於T串的第二、三、四、五位置的字元都與首位「a」相等，那麼可以用首位next[1]的值去取代與它相等的後續字元的next[j],那麼next數組為{0,0,0,0,0,5};
在求解nextVal數組的5種情況
7. KMP演算法中的next數組值的疑問
問題1數組下標是從1開始計算 問題2數組下標從0開始
8. KMP演算法中的next數組如何計算
next[i]表示的是：
在第i個字元前面的i-1個字元裡面，
從開頭開始的1個字元與最後1個字元是否相等，若不是，則next[i]=0,否則繼續看下面；
從開頭開始的2個字元與最後2個字元是否相等，若不是，則next[i]=1,否則繼續看下面；
從開頭開始的3個字元與最後3個字元是否相等，若不是，則next[i]=2,否則繼續看下面；
……
就是這樣的判斷取值。
它的意思就是如果到了某個字元不匹配的情況時候，你就可以直接把模式串拖到從開頭開始的那next[i]個字元等於當前字元的前next[i]個字元的地方，這樣就少了很多重復的無效的比較和移動。
9. kmp演算法什麼意思
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，繼續進行比較。
10. 已知一個模式串T="aaaba",則在KMP演算法中,其next數組中的值是 (
abaabcac
01122312
前兩個字母next序列分別為01,直接寫上
第三個"a" 時，它前一個字母為b,從頭開始字母為a, a!=b所以為1
第四個"a" 時，前字母為a,從頭開始字母為a,a=a,所以值為1＋1=2（相等時為串長加1）
第五個"b"，前個字母為a,從頭開始a,a=a,為2
第六個"c",前個字母為b,再往前是a,ab,從頭開始ab串，ab=ab，因此值為2＋1＝3
第七個字母為"a",前個字母為c,與從頭開始的第一個字母不相等，所以為1
第八個為"c",前個字母為a,與開始第一個字母相等，因此為2
則返回邏輯「真（TRUE）」，反之返回邏輯「假（FALSE）」。