KMP模版帶解釋過程

KMP算法

當比對字元串是ababcabaa時，被比對的字元串是ababababcabaab時
 	q:ababababcabaab
    p:ababcabaa
 先模拟一下簡單比對
    ababababcabaab
    ababcabaa
    11110
    ababababcabaab
     ababcabaa
     0
    ababababcabaab
      ababcabaa
      11110
    .......
比對過程：
1. 當從被比對字元串的第一個字元開始與比對，當被比對字元串和比對字元串中的字元不同的時候為0 比對失敗
2. 然後從被比對字元串的後一個字元開始再與比對字元串一個個比對，速度很慢
3. KMP算法可以加速比對，通過移動比對字元串
 
KMP算法先處理比對字元串 計算next數組
1.首先初始化next數組都為-1
2.從比對字元串下标為1的字元i開始，取出上個字元i-1的next值j，
3.若p[j+1] != p[i]且j！=-1，往前尋找 j=next[j]
4.若p[j+1] == p[i],next[i] = j+1
 
 看一下例子 p=abcaba，預設為-1，-1，-1，-1，-1，-1
 i = 1 j = next[0] = -1 不滿足操作3 p[j+1] != p[i] 不滿足操作4 next值不變
 i = 2 j = next[1] = -1 不滿足操作3 p[j+1] != p[i] 不滿足操作4 next值不變
 i = 3 j = next[2] = -1 不滿足操作3 p[j+1] == p[i] 滿足操作4 next[i]=j+1 next[3]=0
 i = 4 j = next[3] = 0  p[j+1] == p[i] 不滿足操作3 滿足操作4 next[i]=j+1 next[4]=1
 i = 5 j = next[4] = 1  p[j+1] != p[i] 滿足操作3 j = next[j] = -1 不滿足操作3 p[j+1] == p[i] 滿足操作4 next[5]=0
 最後next數組為[-1,-1,-1,0,1,0]
 
KMP比對操作：
1. j從-1開始，周遊被比對字元串q
2. 若 j != -1 且 p[j+1] != q[i]  則 j= next[j] 調整p的下标繼續比對
3. 若比對則比對字元個數++
 
ababcabaa的next數組為[-1,-1,0,1,-1,0,1,2,0]
根據KMP再模拟一下比對
q   ababababcabaab
p   ababcabaa
    11110
當 j = 3,i = 4 時 p[j+1] != q[i]，滿足操作2  j= next[j] = 1，于是比對變成
q   ababababcabaab
p     ababcabaa
       111
繼續判斷當 j = 1，i = 4時，發現滿足操作3,比對字元++，直到
q   ababababcabaab
p     ababcabaa
      11110
重複之前的操作，找到比對，發現速度很快
q   ababababcabaab
p       ababcabaa
        111111111
 
模版代碼
class Solution {
public:
    bool kmp(const string& q, const string& p) {
        int m = q.size();
        int n = p.size();
        vector<int> next(n,-1);
        for(int i = 1;i < n; i++){
            int j = next[i-1];
            while(j != -1 && p[j+1] != p[i]){
                 j = next[j];
            }
            if(p[j+1] == p[i]){
                next[i] = j+1;
            }
        }
        int j = -1;
        for(int i = 1;i < m-1; i++){
            while(j != -1 && p[j+1] != q[i]){
                j = next[j];
            }
            if(p[j+1] == q[i]){
                j++;
                if(j == n-1){
                    return true;
                }
            }
        }
        return false;
    }
};
           

今天也是愛zz的一天哦！