其實(shí)嚴(yán)蔚敏版《數(shù)據(jù)結(jié)構(gòu)》的4.3節(jié)已經(jīng)把推導(dǎo)過程講得很清楚了（不過沒講nextval），個(gè)人覺得比算法導(dǎo)論上要好懂。雖然本人也是花了好多時(shí)間才搞清楚，原因還是嚴(yán)蔚敏書上的偽碼真是太差，而且每次理論看到一半時(shí)就想去看偽碼，結(jié)果還是不懂。這次靜下心來把書上理論部分一步步看下來，發(fā)現(xiàn)其實(shí)挺簡(jiǎn)單的。
這里自己簡(jiǎn)要推導(dǎo)下并給出C++實(shí)現(xiàn)。網(wǎng)上的教程一搜一大把，這里主要還是便于自己記憶。
next數(shù)組含義
如上圖所示，樸素匹配算法在匹配失敗時(shí)，模式串向右移動(dòng)1位。而KMP匹配則可能向右移動(dòng)多位，因?yàn)榛疑糠謆cab中cab和ab都是以c和a開頭的，不可能與b相等，KMP匹配做了個(gè)預(yù)處理（即求解next數(shù)組），使得能在此時(shí)知道移動(dòng)多少位。
下文中用
s表示匹配串，p表示模式串，a[i..j]表示數(shù)組a[]的一個(gè)閉區(qū)間子序列a[i],a[i+1],...,a[j]當(dāng)前狀態(tài)：
s[i-k..i-1]=p[0..k-1]，而s[i]!=p[k]。則
j=next[k]<k代表下次將s[i]和p[j]進(jìn)行比較。既然如此，
p[j]的前綴就和s[i]的前綴必須相同，即s[i-j..i-1]=p[k-j..k-1]由于
j<k，結(jié)合當(dāng)前狀態(tài)，有s[i-j..j-1]=p[0..j-1]，因?yàn)榈忍?hào)兩邊分別為s[i-k..i-1]和p[0..k-1]的前綴。因此有
p[0..j-1]=p[k-j..k-1]，問題可以變成求解p[0..k-1]的前綴=后綴時(shí)的最長長度（這話有點(diǎn)繞= =），比如對(duì)"abcab"，最長長度是2，對(duì)應(yīng)此時(shí)的前綴和后綴均為"ab"。
KMP算法實(shí)現(xiàn)
size_t search_kmp(const std::string& src, const std::string& pattern, size_t pos = 0) {
auto next = get_next(pattern); // 關(guān)鍵!!!
size_t i = pos; // 匹配串當(dāng)前字符序號(hào)
size_t j = 0; // 模式串當(dāng)前字符序號(hào)
while (i < src.size() && j < pattern.size()) {
if (src[i] == pattern[j]) {
i++;
j++;
} else {
j = next[j];
// j == -1即整個(gè)模式串要與s[i+1..n]進(jìn)行匹配
if (j == static_cast<size_t>(-1)) {
i++;
j = 0;
}
}
}
// -1代表查找失敗
return (j < pattern.size()) ? -1 : (i - pattern.size());
}
從上述代碼中可以進(jìn)一步看到next數(shù)組的作用，于是問題關(guān)鍵就在于求解next數(shù)組，這也是很多筆試題只要求算next數(shù)組的原因。
next數(shù)組求解方法
樸素的求法是找到所有等長前綴和后綴，然后一一比較。但無疑這種做法效率極其低下的。這里用數(shù)學(xué)歸納法可以推導(dǎo)遞推式。
-
next[0]=-1，next[1]=0。因?yàn)槿绻Ｊ酱?位p[0]就匹配失敗，那么就會(huì)向右移動(dòng)1位，p[0]與s[i+1]比較，等價(jià)于p[-1]與s[i]比較。而p[1]匹配失敗時(shí)，會(huì)用p[0]和s[i]進(jìn)行比較。 - 設(shè)
next[k]=j，則有p[0..j]=p[k-j..k]，且不存在更大的j'使得p[0..j ']=p[k-j'..k]?，F(xiàn)在求解j'=next[k+1]，分類討論
2.1p[j+1]=p[k+1]，則有p[0..j+1]=p[k-j..k+1]，因此next[k+1]=next[k]+1。
2.2p[j+1]!=p[k+1]，這里就是求解next的關(guān)鍵部分了。此時(shí)可以把p[0..k+1]看成匹配串，p[k+1-j'..k+1]看出模式串，該模式串等于p[0..j'-1]。因此p[0..j'-2]=p[k-j'..k]，可以用同樣的方法來滑動(dòng)該模式串。
比如
現(xiàn)在求解next[6]，可以發(fā)現(xiàn)p[2]!=p[6]，然后就可以再比較p[0]和p[6]。
next數(shù)組求解實(shí)現(xiàn)
inline std::vector<int> get_next(const std::string& pattern) {
int n = pattern.size();
if (n == 0)
return {};
if (n == 1)
return { -1 };
std::vector<int> next(n);
next[0] = -1;
next[1] = 0;
int k = next[1];
for (int i = 2; i < n; i++) {
if (pattern[k] == pattern[i - 1]) {
k = next[i] = next[i - 1] + 1;
} else {
while (true) {
k = next[k];
if (k == -1 || pattern[k] == pattern[i - 1])
break;
}
next[i] = ++k;
}
}
return next;
}
注意while語句部分，可以簡(jiǎn)化成像嚴(yán)蔚敏書上偽碼一樣，但是不如上面代碼那么直觀。
至于考題上由于字符串下標(biāo)一般從1開始，所以next數(shù)組的每個(gè)值都要加1。
nextval數(shù)組
nextval數(shù)組和next數(shù)組的關(guān)系如下
if (p[i] != p[next[i]])
nextval[i] = next[i];
else
nextval[i] = nextval[next[i]];
具體nextval為何成立暫時(shí)沒找到資料，先應(yīng)付應(yīng)試吧。
