第四章 KMP

作用：快速从主串中找到匹配的字串

分析

1. KMP算法的模式串每次后移，都会将前缀移动到后缀的位置，且移动的过程中不会有遗漏的情况。

2. 寻找到不匹配字符前的最长公共前后缀。
   1. 最长公共前后缀：若不匹配字符前方子串为ABABA，公共前后缀有A(ABABA)(ABABA)、ABA(ABABA)(ABABA)、ABABA(无意义)。
   2. 如果模式串中有多个公共前后缀，选择最长的那一对，即ABA。

3. 若模式串超出主串范围，则匹配失败。

4. 寻找最长公共前后缀时，最长公共前后缀的长度要小于匹配指针左侧模式串子串长度。

5. 模式串的匹配和主串没有关系，只与模式串自身所比较。

6. 所以我们要求出模式串每个位置发生不匹配的时候，该位置之前的最长公共前后缀的长度，方便求出指向主串指针后移的步数（或者可以说模式串向后移动的步数），便可以得到我们常说的next数组。

7. 求解next数组首先要知道以下几个概念

// j: 1 2 3 4 5 6
// P: a b a b a ?
// N: 0 1 1 2 3 4
int GetNext(char ch[], int length, int next[]){
    next[1] = 0;
    int i = 1, j = 0;
    while(i < length){
         // 每个循环next数值最多增1
         if(j == 0 || ch[i]==ch[j]) next[++i] = ++j; 
         else j = next[j];
    }
}

引用

• 「知乎」强烈推荐的KMP讲解