學(xué)習(xí)記錄一下kmp算法，本文主要參考一下幾篇博客。
https://blog.csdn.net/a1b2c3d4123456/article/details/50506454
https://blog.csdn.net/crazy_scott/article/details/79211961
https://blog.csdn.net/qq_37969433/article/details/82947411

KMP算法本質(zhì)上是為了解決字符串匹配的問題。首先我們來看暴力的字符串匹配方法。

1. 暴力匹配

從原字符串開始搜索，若出現(xiàn)不能匹配，則從原搜索位置+1繼續(xù)。時間復(fù)雜度O(m*n)。

雖然前4位一樣但是第5位不一樣，需要從原來的位置+1,再進(jìn)行匹配。

以此類推，直到匹配為止。

/*
檢測從主串strA的pos位置開始，是否有和子串strB匹配,如果有返回匹配開始位置，如果沒有，返回-1
strA:主串
strB:子串
pos:主串開始位置
*/
int getIndex(string strA, string strB, int pos){
    int lenA=strA.size();
    int lenB=strB.size();

    int i=pos,j=0;
    while(i<lenA && j<lenB){
        if(strA[i]==strB[j]){
            i++;
            j++;
        }else{
            i = i-j+1;
            j=0;
        }
    }
    return j==lenB?i-lenB:-1;
}

2. KMP匹配

KMP算法其實就是一種改進(jìn)的字符串匹配算法，關(guān)鍵是利用匹配后失敗的信息，盡量減少模式串（W）與主串（T）的匹配次數(shù)以達(dá)到快速匹配的目的。具體實現(xiàn)就是實現(xiàn)一個next() 函數(shù)，函數(shù)本身包含了模式串的局部匹配信息。時間復(fù)雜度 O(m+n)。 KMP算法利用已經(jīng)部分匹配這個有效信息，保持i指針（主串）不回溯，通過修改j指針，讓模式串盡量地移動到有效的位置，具體可見下面一個例子。

• 比如，Wj處失配，綠色的是Wj，則我們可以確定W1…Wj-1是與Ti…Ti+j-2相對應(yīng)的位置一一相等的;

• 假設(shè)W1…Wj-1中，W1…Wk-1與Wj-k+1…Wj-1是一一相等的，為了下面說的清楚，把這種關(guān)系叫做“首尾重合”部分（字符串前綴與后綴重復(fù)）

• 那么可以推出，W1…Wk-1與Ti…Ti+j-2

• 顯然，接下來要做的就是把模式串右移了，移到哪里就不用多說了：

• 為了表示下一輪比較j定位的地方，我們將其定義為next[j]，next[j]就是第j個元素前j個元素首尾重合部分個數(shù)，當(dāng)然，為了能遍歷完整，首尾重合部分的元素個數(shù)應(yīng)取到最多，即next[j]應(yīng)取盡量大的值。

• 最后，如果我們知道了一個字符串的next值，那么KMP算法也就很好懂了。相比樸素算法，當(dāng)發(fā)生失配時，i不變，j=next[j]就好啦！接下來就是怎么確定next值了。

2.1 Next函數(shù)

#include <vector>
#include <string>
#include <iostream>
using namespace std;


vector<int> kmp_next(string &m){
   vector<int> next(m.size(), 0);
   next[0]=0;
   int temp;
   for(int i=1; i<next.size(); i++){
       temp=next[i-1];
       while(m[i]!=m[temp]&&temp>0) temp=next[temp-1];
       if(m[i]==m[temp]) next[i]=temp+1;
       else next[i]=0;
   }
   return next;
}

bool kmp_search(string text,string m,int &pos){
   vector<int> next=kmp_next(m);
   int tp=0;
   int mp=0;
   for(tp=0; tp<text.size(); tp++){
       while(text[tp]!=m[mp]&&mp) mp=next[mp-1];
       if(text[tp]==m[mp]) mp++;
       if(mp==m.size()){
           pos=tp-mp+1;
           return true;
       }
   }
   return false;
}

int main(){
   int pos;
   if(kmp_search("sdsadabcdef", "abc", pos)) cout << pos << endl;

   return 0;
}