KMP算法（C++实现）

• • 前言
  • KMP的概念
  • • 前后缀的概念
    • 如何求前后缀和next数组（KMP的精髓）
  • tips

学习过kmp算法的大概都知道那种学了忘，忘了又要学，然后学完代码又写不好的反复境地，所以今天下定决心一定要彻底解决KMP算法，以后不会了能让自己快速捡起来。

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

思路就是把这个串的前缀和后缀进行对比，找到最长的相等的前后缀，然后把长度记录到next数组中，用于正式的字符串匹配中。思路都好理解，重点是如何用代码求next数组呢？为什么不同的人求得next数组也不一样呢？（整体右移一位，整体减一，或者不变），大致有这三种next数组的求法。下面在代码中进行仔细的解释。
代码大致的思路就是：
对参数进行初始化
用i，j分别指向后缀的末尾和前缀的末尾。
处理s[i] = s[j] 时的情况
处理s[i] != s[j] 时的情况
给next数组赋值

1. 整体减一的方法：

void getNext(vector &next, const string &s)
{
    next.resize(s.size());
    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]
        //cout << next;
    }
}

2. next数组不变的方法：

void getNext2(vector& next, const string &s)
{
	//注意这里与减一的方法不同的是j从0开始的
    int j = 0;
    next[0] = 0;
    for (int i = 1; i < s.size(); i++)
    {
    	// j要保证大于0，因为下面有取j-1作为数组下标的操作
        while (j > 0 && s[i] != s[j])
        {                    
            j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
        }
        if (s[i] == s[j])
        {
            j++;
        }
        next[i] = j;
        //cout << next;
    }
}

3. next数组整体右移的方法：

void getNext3(vector& next,const string& s){
    int j = 0;
    next[0] = 0;
    for (int i = 1; i < s.size()-1; ++i)
    {
        while (j > 0 && s[i] != s[j])
        {                  
            j = next[j - 1];
        }
        if (s[i] == s[j])
        {
            j++;
        }
        next[i+1] = j;
        cout << next;
    }
}

main函数：

int main(){
    vector next;
    next.resize(6);
    vector next2(6,0);
    vector next3(6,0);
    string s("aabaaf");
    getNext(next,s);
    cout << "**********************n";
    getNext2(next2,s);
    cout << "**********************n";
    getNext3(next3,s);

    //cout << KMP("aabaabaaf","aabaaf");

    return 0;
}

对运算符进行重载：

template
ostream& operator<<(ostream& os,vector x){
    for(auto i : x){
        os << i << " ";
    }
    os << "n";
    return os;
}

有点类似DP算法的思想。
只需要记住j是代表的前缀的末尾，i是代表的后缀的末尾，然后分别处理s[i] ，s[j]相等和不相等的情况就可以了，如果相等，则++i,++j 并把当前j的值赋值给next数组。如果不相等，就j根据next数组的值进行回退，直到退到相等的情况或者是退到了开头，再进行赋值。一定要注意边界问题。