KMP算法（对next数组的回溯理解清楚）

一、概念

• KMP算法是求解主串（以下简称为s）和模式串（以下简称为p）匹配问题的O(n)算法。
• 其核心思想就是，当s[i]和p[j]发生不匹配现象时，i指针不需要回溯，只需j指针回溯。
• 传统的暴力匹配：当s[i]与p[j]不匹配时，i回溯到之前的起点下一个位置，j=0，重新进行匹配，如下图的solution1方式。复杂度为O（n*m），n为主串s长度，m为模式串p长度。
• KMP算法：i不回溯。过程如solution2: 当s[i]与p[j]不匹配时，保持上面不动，移动下面的模式串，使上A与下A对齐，j指向B.
  KMP算法：可以实现复杂度为O(m+n)
  

二、KMP

KMP的模式串分为
1. 最长前缀和最长后缀为0：各元素均不相同
在比较时，实现最大的移动量

2. 最长前缀和最长后缀>0： 前后存在相同的子串
在比较时，移动距离较短(总长度-前后缀长)。下面的模式串移动到与后缀对齐，开始比较。下图：1、2、3、4前后缀相同，将下面的3移动到与2对齐再比较

考察目标字符串ptr：ababaca
这里我们要计算一个长度为m的转移函数next。
next数组的含义就是一个固定字符串的最长前缀和最长后缀相同的长度。
比如：abcjkdabc，那么这个数组的最长前缀和最长后缀相同必然是abc。
cbcbc，最长前缀和最长后缀相同是cbc。
abcbc，最长前缀和最长后缀相同是不存在的。

注意最长前缀：是说以第一个字符开始，但是不包含最后一个字符。
比如aaaa相同的最长前缀和最长后缀是aaa。
对于目标字符串ptr，ababaca，长度是7，所以next[0]，next[1]，next[2]，next[3]，next[4]，next[5]，next[6]分别计算的是
a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀的长度。由于a，ab，aba，abab，ababa，ababac，ababaca的相同的最长前缀和最长后缀是“”，“”，“a”，“ab”，“aba”，“”，“a”,所以next数组的值是****[-1,-1,0,1,2,-1,0]，这里-1表示不存在，0表示存在长度为1，2表示存在长度为3。这是为了和代码相对应。

**

三、代码解析

**
1.求next数组

void cal_next(char *str, int *next, int len)
{
    next[0] = -1;//next[0]初始化为-1，-1表示不存在相同的最大前缀和最大后缀
    int k = -1;//k初始化为-1
    for (int q = 1; q <= len-1; q++)
    {
        while (k > -1 && str[k + 1] != str[q])//如果下一个不同，那么k就变成next[k]，注意next[k]是小于k的，无论k取任何值。
        {
            k = next[k];//往前回溯！！个人感觉这个回溯最难理解
        }
        if (str[k + 1] == str[q])//如果相同，k++
        {
            k = k + 1;
        }
        next[q] = k;//这个是把算的k的值（就是相同的最大前缀和最大后缀长）赋给next[q]
    }
}

1.回溯理解 (后缀的字符串的后缀=前缀的字符串的前缀)
回溯这段个人感觉最难理解。K值表示每个q之前的字符串前后缀最大长度。
回溯目的：之前一直匹配成功，k++，当出现不匹配时，为了充分利用之前已经匹配好的前后缀，紧挨着尾部的后缀与前缀相同，为了看此时后缀右侧（紧挨着尾部的元）还剩多少元与头部相同，因此k=next[k]，看后缀的字符串中的前后缀长度，后缀的字符串的后缀=前缀的字符串的前缀
注：以字符ababaca为例作说明如下，图片较小，请务必放大来看，对理解回溯过程很重要
2.KMP
这个和next很像，next是针对模式串的部分的前后缀相同的特性，来回溯更新next[q]值。而KMP是根据整体模式串p的前后缀相同的特性，来回溯以此来移动 j指针目的

int KMP(char *str, int slen, char *ptr, int plen)
{
    int *next = new int[plen];
    cal_next(ptr, next, plen);//计算next数组
    int k = -1;
    for (int i = 0; i < slen; i++)
    {
        while (k >-1&& ptr[k + 1] != str[i])//ptr和str不匹配，且k>-1（表示ptr和str有部分匹配）
            k = next[k];//往前回溯
        if (ptr[k + 1] == str[i])
            k = k + 1;
        if (k == plen-1)//说明k移动到ptr的最末端
        {
            //cout << "在位置" << i-plen+1<< endl;
            //k = -1;//重新初始化，寻找下一个
            //i = i - plen + 1;//i定位到该位置，外层for循环i++可以继续找下一个（这里默认存在两个匹配字符串可以部分重叠）
            return i-plen+1;//返回相应的位置
        }
    }
    return -1;  
}

3.改进KMP
当模式串存在很多连续相同的元时，aaaab，其next为[-1,0,1,2,-1],
在回溯时，为了去掉相同的路线，next为[-1,-1,-1,-1, -1]