考研復(fù)習(xí)過程中屡穗，看到王道的《數(shù)據(jù)結(jié)構(gòu)》中對(duì)KMP的解釋有感而發(fā)厅目。感覺王道解釋的有點(diǎn)復(fù)雜番枚，然后自己理解了一下，在此寫一點(diǎn)心得
如果我記得沒錯(cuò)损敷，next數(shù)組的獲得的代碼是長這個(gè)樣子的葫笼。
void getNext(char *s, int *next) {
next[1] = 0;
int i = 1;
int j = 0;
while (i < s[0]) {
if (j == 0 || s[i] == s[j]) {
++j; ++i; next[i] = j;
} else
j = next[j];
}
}
接下來把王道《數(shù)據(jù)結(jié)構(gòu)》中的解釋放出來
大家可以嘗試著理解一下，如果覺得這么解釋更容易理解就可以不往下看了..
接下來就是我對(duì)next數(shù)組產(chǎn)生從不同角度的理解
先隨便寫一個(gè)字符串：abcc acab cc
根據(jù)屴致科班應(yīng)有的素質(zhì)路星，應(yīng)該能得出next數(shù)組內(nèi)容為0111 1212 34
步驟為：
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 |
next[0]不存在，next[1]必定等于0（規(guī)定的）
如何求得next[3]诱桂？
若按照王道《數(shù)據(jù)結(jié)構(gòu)》中的步驟洋丐，很難操作，并且與代碼所呈現(xiàn)的邏輯不符挥等，反正我理解起來很別扭垫挨。
但仔細(xì)看代碼，其實(shí)很容易就發(fā)現(xiàn)next[3]的值就是若next[2]==next[1]則next[3] = next[2] + 1触菜。否則九榔，就和string[1]的next值即next[1]值索引的string字符做比較。
此時(shí)
next[1] = 0，而規(guī)則就是若比到next值出現(xiàn)0時(shí)哲泊，直接得出下一個(gè)next值為1剩蟀，或者說同時(shí)令index和next[index]加1（next是根據(jù)當(dāng)前所在的值，此時(shí)next = 0）
于是就得出next[3]=1切威。
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 | 1 |
接下來同樣讓string[3]與string[next[3]]（即string[1]）相比育特，不等，next為0先朦，加一缰冤。。喳魏。
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 | 1 | 1 |
同理棉浸，注意next[5]的1是根據(jù)string[4]與string[next[4]]（即string[1]）相比較得出的
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 | 1 | 1 | 1 |
然后string[5]與string[next[5]]（即string[1]）相比，相等刺彩，于是index++迷郑，next[index]=next[index-1]+1 （就是加了一）
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 | 1 | 1 | 1 | 2 |
然后理所應(yīng)當(dāng)?shù)?code>string[6]與string[next[6]]（即string[2]）相比，不一樣创倔，轉(zhuǎn)而string[6]與string[next[next[6]]]（即string[1]）嗡害，又不同，而此時(shí)next [next[next[6]]] == 0畦攘，于是next[++index] = next[next[next[6]]] + 1
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 | 1 | 1 | 1 | 2 | 1 |
霸妹。。知押。
叹螟。。朗徊。
首妖。偎漫。爷恳。
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| string[index] | a | b | c | c | a | c | a | b | c | c |
| next[index] | 0 | 1 | 1 | 1 | 1 | 2 | 1 | 2 | 3 | 4 |
