KMP算法

KMP算法不算是多难的算法，它的困难之处在于没有人愿意将它讲清楚

先贴一个感觉比较清楚的教程：KMP算法最浅显理解——一看就明白。这里面的代码相对通俗易懂。

下面是自己实现时的感受：

算法的原理还是比较好懂的，但在看别人代码时最最难受的事情就是next数组的确定…不同的人有不同的规则。比如next[i] 的值为 n，有可能是指前i+1个字符有长度为n的重复串，也有可能值前i+1个字符有长度为n+1的字符串，也有可能指前i个字符有长度为n的字符串，某些人还会特别的把next[0]设定为-1…
关键的关键，是设定这种规则的人，还往往不把规则说清楚！！！（读这一大串字就够痛苦了，更别说我在阅读他人代码实现时是有多痛苦了☹）

下面的代码依照一般教科书上的官方版本，next[i] = n,表示前i+1个（注意下标从0到i共i+1）字符有长度为n+1的重复串，没有其他特殊约定。

|模式串:|a|b|a|b|a|c|a|
|next[i]|-1|-1|0|1|2|-1|0|

#include<string>
#include<iostream>
using namespace std;

int getNext(string target,int* next)
{
    next[0] = -1;
    int k = -1; //重复子串长度为k
    for (int i = 1; i < target.size(); ++i)//考虑：终点是target.size()-1还是target.size()-2
    {
        while (~k && (target[k + 1] != target[i]))//一定要注意条件~k，否则当没有重复子串时就会无限循环
            k = next[k];    //k = next[k]是代码的核心
    //循环跳出后，有两种可能：k=-1或target[k+1]==target[i] 这两种情况下，若target[k + 1] == target[i]，字串长度均要+1
        if (target[k + 1] == target[i])
            ++k;
        next[i] = k;
    }
    return 0;
}
/*上面这个函数函数处理的效果：
以target = "abbcabbba"为例，它的最终得到的next数组为：{-1,-1,-1,-1,0,1,2,-1,0}
*/


int KMP(string source, string target)
{
    int* next = new int[target.size()];
    getNext(target, next);
    int i = 0, j = -1;//j为target（模式串）的指针。
    while (i < source.size())
    {
        if (source[i] == target[j+1])//若两指针所指元素相等，显然要右移。
        {
            ++i;
            ++j;
        }
        else if (j == -1)//说明没有重合子串，只能让目标串的指针加1
            ++i;
        else
            j = next[j];//source[i] != target[j]找到j的下一个位置
        if (j == target.size()-1)//匹配完毕
            break;
    }
    if (i >= target.length())
    {
        delete[]next;
        return i - target.length();
    }
    else
    {
        delete[]next;
        return -1;
    }
}

int main()
{
    int next[20];
    getNext("ABACDABABC", next);
    for (int i = 0; i < 10; ++i)
        cout << " " << next[i];
    cout << "起始位置：" << KMP("abababc", "bc");
}