对于KMP算法的理解及C++代码实现

1、基本概念

前缀：包含首字母，不包含尾字母的所有子串

后缀：包含尾字母，不包含首字母的所有子串

文本串：a a b a a b a a f

模式串：a a b a a f

2、求最长相等的前后缀的长度:

a - 0 aa -1 aab - 0 aaba -1 aabaa - 2 aabaaf - 0

模式串：a a b a a f

前缀表：0 1 0 1 2 0

3、如何用前缀表匹配？

文本串：a a b a a b a a f

下标       0 1 2 3 4 5 

模式串：a a b a a f

              0 1 0 1 2 0

       前缀表是用来退回的，它记录了模式串与文本串不匹配的时候，模式串应该从哪里开始重新匹配。前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

        找到最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面从新匹配就可以了。

        找到不匹配的位置，此时要看它的前一个字符的前缀表的值数是多少。（数值代表有多大长度的相同前后缀）

4、前缀表与next数组

        next存的是子串前后缀相等的最大长度，有三种实现方式，仅表示遇到冲突时，去找的方式不一样。 next数组就可以是前缀表，但很多实现都是把前缀表统一减一（或者右移一位，初始位置为-1）之后作为next数组。（next数组告诉我们要回退到哪里！）

下标       0  1  2  3  4  5 

模式串：a  a  b  a  a  f

前缀表:  0  1  0  1  2  0

减一：  -1  0 -1  0  1 -1     

右移：  -1  0  1  0  1  2 

       减一优化了next数组，不右移的情况下，0号位置要写额外的判断条件。

5、构造next数组

构造next数组其实就是计算模式串前缀表的过程，主要有以下三步:

（1）初始化；

（2）处理前后缀不相同的情况；

（3）处理前后缀相同的情况；

（4）更新next数组的值。

以前缀表减一之后的next数组为例：

1、初始化：
   定义两个指针i和j，j指向前缀起始位置，i指向后缀起始位置；
   对next数组进行初始化赋值，如下
    int j = -1;  next[0] = j;
    j = 0;  next[0] = j;
  j也表示i之前，包括i子串的最长相等前后缀的长度
  i和j要从字符串下标位置的角度看

2、处理前后缀不相等
  不匹配，j向前回退；看它的前一位的next数组的值，对应的值就是它要回退的下标
  因为j初始化为-1，那么i就从1开始，进行s[i] 与 s[j+1]的比较。
  所以遍历模式串s的循环下标i 要从 1开始，代码如下：
  for(int i = 1; i < s.size(); i++) {
  
while(j >= 0; && S[i] != S[j+1])
{
    j = next[j];  //向前回退
    //next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度
}

3、处理前后缀相同的情况
    如果s[i] 与 s[j + 1] 相同，那么就同时向后移动i 和j 说明找到了相同的前后缀，同时还要将j（前缀的长度）赋给next[i], 因为next[i]要记录相同前后缀的长度。
    if (s[i] == s[j + 1]) { // 找到相同的前后缀
        j++;
    }
    next[i] = j;

 最后整体构建next数组的函数代码如下：

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]
    }
}

6、C++ 代码实现 

前缀表统一减一：

class Solution {
public:
    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]
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = -1; // // 因为next数组里记录的起始位置为-1
        for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
            while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
                j = next[j]; // j 寻找之前匹配的位置
            }
            if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
                j++; // i的增加在for循环里
            }
            if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};