1.概念解析

　前置：

　　将原串称之为 文本串，匹配串称之为 模式串。

　　KMP的实质其实就是：利用已经匹配的信息，来加速查找的过程。

　　对于暴力解法而言，当我进行模式串匹配时，遇到一个不匹配的字符，那么只能一步一步往下滑动，然后重新匹配。

　　但是对于KMP算法而言，利用到了 前缀子串和后缀子串的匹配信息。

　什么是前缀子串和后缀子串:

　　以字符串 abc 为例：{ 'ab' , 'a' } 就是它的前缀集合，{ 'bc' , 'c' } 就是它的一个后缀集合；

　　But，注意了'abc'本身不算在前后缀里

　　定义：

　　前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
　　后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

　　那么对于KMP算法而言就是要用到 模式串最长公共前后缀 来加快模式匹配

　　注意黑体，是模式串的最长前后缀，那么这个最长公共前后缀的求取是和文本串没有关系的！

　　那么我们只需要利用一个前缀表next来存储每个位置的最长公共前后缀即可，例如对于字符串 "abababca"

　　注：pmt是原始的前缀表，next是减1后的前缀表；二者原理一样，只是实现代码的方式略有区别罢了

　　这里解释用pmt解释（易懂一些），代码实现采用了next（减1法）

　　那么例如对于 index=0 而言，a是首位，没有前后缀，那么就是 0，index=2 而言呢，前后各一个 'a' ，故最长公共前后缀为1.以此类推

2.代码实现

　　这里采用减一法来实现：

class Solution {
public:
    void getPreArray(int* next, string& needle)
    {
        int j = -1;   //j<0其实本质对应了没有匹配的前后缀
        next[0] = -1;
        for (int i = 1; i < needle.size(); ++i)
        {
            //这里为什么j>=0 ? 因为j>=0表明了i前面一个字符至少有一个匹配的
            //否则 i-1 的位置和第一个字符都不匹配，直接拿 i 位置和第一个字符比较即可
            while (j >= 0 && needle[i] != needle[j + 1])
                j = next[j];
            //当needle[i] != needle[j + 1]时呢，我们就要利用前缀表移动位置了！
            //j=next[j] 其实就是移动到公共前后缀的下一位
            //为什么要用while循环呢？ 因为这个位置的公共前后缀下一位不一定匹配呀！我们要求匹配的前缀表
            
            //如果等于，就说明有字符匹配了，那么说明至少匹配一个字符（例如头部）,j++咯
            if (needle[i] == needle[j + 1]) 
                
                j++;
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        int j = -1;
        int* next = new int[needle.size()];
        getPreArray(next, needle);
        for (int i = 0; i < haystack.size(); ++i)
        {
            while (j >= 0 && haystack[i] != needle[j + 1])
                j = next[j];
            if (haystack[i] == needle[j + 1])
                ++j;
            if (j == (needle.size() - 1))
                return i;
        }
        return -1;
    }
};