我覺得這句話說的很好：
kmp算法關(guān)鍵在于：在當(dāng)前對(duì)文本串和模式串檢索的過程中，若出現(xiàn)了不匹配，如何充分利用已經(jīng)匹配的部分，來繼續(xù)接下來的檢索。

暴力解決字符串匹配

暴力解法就是兩層for循環(huán),每次都一對(duì)一的匹配，如果匹配錯(cuò)誤就文本串開始位置加1，繼續(xù)下一次

前綴表的作用

前綴表的作用就是當(dāng)前位置匹配失敗之后，通過前綴表記錄的數(shù)字來去找到模式串中最合適的位置去重新開始下一次匹配，也就是說，匹配到當(dāng)前位置失敗，通過前綴表跳到前面位置繼續(xù)匹配。

我們一個(gè)一個(gè)匹配，如果出現(xiàn)不匹配，這時(shí)候我們希望通過已經(jīng)匹配過的字符串，找到其相同的前綴與后綴，來繼續(xù)接下來的匹配。

那我們?cè)撊绾稳ビ?jì)算這個(gè)前綴字串與后綴字串在每個(gè)位置的最大值，來去繼續(xù)模式串匹配呢？就是接下來的前綴表的計(jì)算（也就是很多KMP算法中next數(shù)組的計(jì)算）

前綴表的計(jì)算（next數(shù)組計(jì)算）

• 什么是前綴？
  前綴就是一個(gè)字符串不包括最末尾的字符從第一個(gè)開始的所有連續(xù)字串
  主串：aabaac
  前綴：a 、aa 、aab 、aaba 、aabaa
• 什么是后綴？
  后綴就是一個(gè)字符串不包含第一個(gè)字符，每次以末尾結(jié)尾的連續(xù)字串
  主串：aabaac
  后綴：c 、ac 、aac 、baac 、abaac
• 如何計(jì)算前綴表？
  

如何使用前綴表？

在KMP算法中，一般的next數(shù)組會(huì)直接使用前綴表，也可能在前綴表的基礎(chǔ)上改進(jìn)一點(diǎn)，但是最終的思路都是圍繞前綴表展開，比如有些實(shí)現(xiàn)方法是把前綴表統(tǒng)一減一或者整體右移一位，初始位為-1。

時(shí)間復(fù)雜度：主串與模式串匹配過程最多為O(N)，模式串的next數(shù)組生成為O(M),所以最后的時(shí)間復(fù)雜度可以為O(N+M)，相較于暴力寫法的O(N*M)，KMP算法還是極大的提高了檢索的效率。

構(gòu)造next數(shù)組

構(gòu)造next數(shù)組其實(shí)就是計(jì)算模式串s，前綴表的過程。 主要有如下三步：

1. 初始化
2. 處理前后綴不相同的情況
3. 處理前后綴相同的情況

初始化：
定義兩個(gè)指針i和j，j指向前綴末尾位置，i指向后綴末尾位置。
然后還要對(duì)next數(shù)組進(jìn)行初始化賦值，如下：

int j = -1;
next[0] = j;

處理前后綴不相同的情況：
因?yàn)閖初始化為-1，那么i就從1開始，進(jìn)行s[i] 與 s[j+1]的比較。
所以遍歷模式串s的循環(huán)下標(biāo)i 要從 1開始，代碼如下：

for (int i = 1; i < s.size(); i++) {

如果 s[i] 與 s[j+1]不相同，也就是遇到 前后綴末尾不相同的情況，就要向前回退。next[j]就是記錄著j（包括j）之前的子串的相同前后綴的長度。那么 s[i] 與 s[j+1] 不相同，就要找 j+1前一個(gè)元素在next數(shù)組里的值（就是next[j]）。
回退代碼：

while (j >= 0 && s[i] != s[j + 1]) { // 前后綴不相同了
    j = next[j]; // 向前回退
}

處理前后綴相同的情況
如果 s[i] 與 s[j + 1] 相同，那么就同時(shí)向后移動(dòng)i 和j 說明找到了相同的前后綴，同時(shí)還要將j（前綴的長度）賦給next[i], 因?yàn)閚ext[i]要記錄相同前后綴的長度。

if (s[i] == s[j + 1]) { // 找到相同的前后綴
    j++;
}
next[i] = j;

構(gòu)建next數(shù)組最終代碼：

void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i從1開始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后綴不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后綴
            j++;
        }
        next[i] = j; // 將j（前綴的長度）賦給next[i]
    }
}

本文主要是看了代碼隨想錄的有感理解+畫圖????

KMP算法題目：leetcode -28

28.找出字符串中第一個(gè)匹配項(xiàng)的下標(biāo)
給你兩個(gè)字符串 haystack 和 needle ，請(qǐng)你在 haystack 字符串中找出 needle 字符串的第一個(gè)匹配項(xiàng)的下標(biāo)（下標(biāo)從 0 開始）。如果 needle 不是 haystack 的一部分，則返回 -1 。

示例 1：

輸入：haystack = “sadbutsad”, needle = “sad”
輸出：0
解釋：“sad” 在下標(biāo) 0 和 6 處匹配。
第一個(gè)匹配項(xiàng)的下標(biāo)是 0 ，所以返回 0 。文章來源地址http://www.zghlxwxcb.cn/news/detail-420640.html

class Solution {
public:
    void Getnext(string s, vector<int>& next)
    {
        int j=0;
        next[j]=0;
        for(int i=1;i<next.size();i++)
        {
            while(j>0 && s[i]!=s[j])
            {
                j=next[j-1];
            }
            if(s[i]==s[j])
            {
                j++;
            }
            next[i]=j;
        }
    }
    int strStr(string haystack, string needle) {
        vector<int> next(needle.size(),0);
        Getnext(needle,next);
        int j=0;
        for(int i=0;i<haystack.size();i++)
        {
            while(j>0 && haystack[i] != needle[j])
            {
                j=next[j-1];
            }
            if(haystack[i]==needle[j])
            {
                j++;
            }
            if(j==needle.size())
            {
                return i-needle.size()+1;
            }
        }
        return -1;        
    }
};

到了這里，關(guān)于KMP算法原理原來這么簡單的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！