五．其他表示模式值的方法
上面那種串的模式值表示方法是最優秀的表示方法，從串的模式值我們可以得到很多資訊，以下稱為第一種表示方法。第二種表示方法，雖然也定義next[0]= -1,但後面絕不會出現-1，除了next[0]，其他模式值next[j]=k(0≤k<j)的意義可以簡單看成是：下标為j的字元的前面最多k個字元與開始的k個字元相同，這裡并不要求T[j] != T[k]。其實next[0]也可以定義為0（後面給出的求串的模式值的函數和串的模式比對的函數，是next[0]=0的），這樣，next[j]=k(0≤k<j)的意義都可以簡單看成是：下标為j的字元的前面最多k個字元與開始的k個字元相同。第三種表示方法是第一種表示方法的變形，即按第一種方法得到的模式值，每個值分别加1，就得到第三種表示方法。第三種表示方法，我是從論壇上看到的，沒看到詳細解釋，我估計是為那些這樣的程式設計語言準備的：數組的下标從1開始而不是0。
下面給出幾種方法的例子：
表一。
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| T | a | b | a | b | c | a | a | b | c |
| (1) next | -1 | -1 | 2 | -1 | 1 | 2 | |||
| (2) next | -1 | 1 | 2 | 1 | 1 | 2 | |||
| (3) next | 1 | 1 | 3 | 2 | 1 | 3 |
第三種表示方法
,
在我看來，意義不是那麼明了，不再讨論。
表二。
| 下标 | 1 | 2 | 3 | 4 | |
| T | a | b | c | A | c |
| (1)next | -1 | -1 | 1 | ||
| (2)next | -1 | 1 |
表三。
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| T | a | d | C | a | d | C | a | d |
| (1)next | -1 | -1 | -1 | |||||
| (2)next | -1 | 1 | 2 | 3 | 4 |
對比
串的模式值第一種表示方法和第二種表示方法，看表一：
第一種表示方法
next[2]= -1,
表示
T[2]=T[0]
，且
T[2-1] !=T[0]
第二種表示方法
next[2]= 0,
表示
T[2-1] !=T[0],
但并不管
T[0]
和
T[2]
相不相等。
第一種表示方法
next[3]= 0,
表示雖然
T[2]=T[0]
，但
T[1] ==T[3]
第二種表示方法
next[3]= 1,
表示
T[2] =T[0],
他并不管
T[1]
和
T[3]
相不相等。
第一種表示方法
next[5]= -1,
表示
T[5]=T[0]
，且
T[4] !=T[0]
，
T[3]T[4] !=T[0]T[1]
，
T[2]T[3]T[4] !=T[0]T[1]T[2]
第二種表示方法
next[5]= 0,
表示
T[4] !=T[0]
，
T[3]T[4] !=T[0]T[1]
，
T[2]T[3]T[4] !=T[0]T[1]T[2]
，但并不管
T[0]
和
T[5]
相不相等。換句話說：就算
T[5]==’x’,
或
T[5]==’y’,T[5]==’9’,
也有
next[5]= 0
。
從這裡我們可以看到：串的模式值第一種表示方法能表示更多的資訊，第二種表示方法更單純，不容易搞錯。當然，用第一種表示方法寫出的模式比對函數效率更高。比如說，在串
S=
“
adCadCBdadCadCad 9876543
”中比對串
T=
“
adCadCad
”
,
用第一種表示方法寫出的模式比對函數
,
當比較到
S[6] != T[6]
時，取
next[6]= -1
（表三）
,
它可以表示這樣許多資訊：
S[3]S[4]S[5]==T[3]T[4]T[5]==T[0]T[1]T[2]
，而
S[6] != T[6]
，
T[6]==T[3]==T[0]
，是以
S[6] != T[0],
接下來比較
S[7]
和
T[0]
吧。如果用第二種表示方法寫出的模式比對函數
,
當比較到
S[6] != T[6]
時，取
next[6]= 3
（表三）
,
它隻能表示：
S[3]S[4]S[5]== T[3]T[4]T[5]==T[0]T[1]T[2]
，但不能确定
T[6]
與
T[3]
相不相等，是以，接下來比較
S[6]
和
T[3];
又不相等，取
next[3]= 0
，它表示
S[3]S[4]S[5]== T[0]T[1]T[2]
，但不會确定
T[3]
與
T[0]
相不相等，即
S[6]
和
T[0]
相不相等，是以接下來比較
S[6]
和
T[0]
，确定它們不相等，然後才會比較
S[7]
和
T[0]
。是不是比用第一種表示方法寫出的模式比對函數多繞了幾個彎。
為什麼，在講明第一種表示方法後，還要講沒有第一種表示方法好的第二種表示方法？原因是：最開始，我看嚴蔚敏的一個講座，她給出的模式值表示方法是我這裡的第二種表示方法，如圖：
她說：“
next
函數值的含義是：當出現
S[i] !=T[j]
時，下一次的比較應該在
S[i]
和
T[next[j]]
之間進行。”雖簡潔，但不明了，反複幾遍也沒明白為什麼。而她給出的算法求出的模式值是我這裡說的第一種表示方法
next
值，就是前面的
get_nextval()
函數。比對算法也是有瑕疵的。于是我在這裡發帖說她錯了：
現在看來，她沒有錯，不過有張冠李戴之嫌。我不知道，是否有人第一次學到這裡，不參考其他資料和明白人講解的情況下，就能搞懂這個算法（我的意思是不僅是算法的大緻思想，而是為什麼定義和例子中
next[j]=k(0
≤
k<j)
，而算法中
next[j]=k(-1
≤
k<j)
）。憑良心說：光看這個講座，我就對這個教受十分敬佩，不僅講課講得好，聲音悅耳，而且這門課講得層次分明，恰到好處。在KMP這個問題上出了點小差錯，可能是編書的時候，在這本書上抄下了例子，在那本書上抄下了算法，結果不怎麼對得上号。因為我沒找到原書，而據有的網友說，書上已不是這樣，也許吧。說起來，教授們研究的問題比這個高深不知多少倍，哪有時間推演這個小算法呢。總之，瑕不掩玉。
void myget_nextval(const char *T, int next[])
{
// 求模式串T的next函數值（第二種表示方法）并存入數組 next。
int j = 1, k = 0;
next[0] = 0;
while ( T[j] != '\0' )
{
if(T[j] == T[k])
{
next[j] = k;
++j; ++k;
}
else if(T[j] != T[0])
{
next[j] = k;
++j;
k=0;
}
else
{
next[j] = k;
++j;
k=1;
}
}//while
for(int i=0;i<j;i++)
{
cout<<next[i];
}
cout<<endl;
}// myget_nextval ![七牛雲-C#SDK-上傳-前期準備[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)