其實嚴蔚敏版《數(shù)據(jù)結(jié)構(gòu)》的4.3節(jié)已經(jīng)把推導過程講得很清楚了（不過沒講nextval）囱井，個人覺得比算法導論上要好懂。雖然本人也是花了好多時間才搞清楚盹靴，原因還是嚴蔚敏書上的偽碼真是太差，而且每次理論看到一半時就想去看偽碼，結(jié)果還是不懂崖技。這次靜下心來把書上理論部分一步步看下來，發(fā)現(xiàn)其實挺簡單的钟哥。
這里自己簡要推導下并給出C++實現(xiàn)迎献。網(wǎng)上的教程一搜一大把，這里主要還是便于自己記憶腻贰。

next數(shù)組含義

KMP算法實現(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;  // 匹配串當前字符序號
    size_t j = 0;  // 模式串當前字符序號
    while (i < src.size() && j < pattern.size()) {
        if (src[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
            // j == -1即整個模式串要與s[i+1..n]進行匹配
            if (j == static_cast<size_t>(-1)) {
                i++;
                j = 0;
            }
        }
    }
    // -1代表查找失敗
    return (j < pattern.size()) ? -1 : (i - pattern.size());
}

從上述代碼中可以進一步看到next數(shù)組的作用歉摧，于是問題關(guān)鍵就在于求解next數(shù)組，這也是很多筆試題只要求算next數(shù)組的原因。

next數(shù)組求解方法

樸素的求法是找到所有等長前綴和后綴叁温，然后一一比較再悼。但無疑這種做法效率極其低下的。這里用數(shù)學歸納法可以推導遞推式膝但。

1. next[0]=-1冲九，next[1]=0。因為如果模式串第1位p[0]就匹配失敗跟束，那么就會向右移動1位莺奸，p[0]與s[i+1]比較，等價于p[-1]與s[i]比較冀宴。而p[1]匹配失敗時灭贷，會用p[0]和s[i]進行比較。
2. 設(shè)next[k]=j略贮，則有p[0..j]=p[k-j..k]甚疟，且不存在更大的j'使得p[0..j ']=p[k-j'..k]。現(xiàn)在求解j'=next[k+1]逃延，分類討論
   2.1 p[j+1]=p[k+1]古拴，則有p[0..j+1]=p[k-j..k+1]，因此next[k+1]=next[k]+1真友。
   2.2 p[j+1]!=p[k+1]黄痪，這里就是求解next的關(guān)鍵部分了。此時可以把p[0..k+1]看成匹配串盔然，p[k+1-j'..k+1]看出模式串桅打，該模式串等于p[0..j'-1]。因此p[0..j'-2]=p[k-j'..k]愈案，可以用同樣的方法來滑動該模式串挺尾。
   比如
   
   
   現(xiàn)在求解next[6]，可以發(fā)現(xiàn)p[2]!=p[6]站绪，然后就可以再比較p[0]和p[6]遭铺。

next數(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語句部分，可以簡化成像嚴蔚敏書上偽碼一樣恢准，但是不如上面代碼那么直觀魂挂。
至于考題上由于字符串下標一般從1開始，所以next數(shù)組的每個值都要加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為何成立暫時沒找到資料涂召，先應付應試吧。