白驹过隙，这篇文章距今已有一年以上的历史。技术发展日新月异，文中的观点或代码很可能过时或失效，请自行甄别：）

首先先对D.E.Knuth,J.H.Morris以及V.R.Pratt这三位老前辈致敬,发明了这个高效的算法.

来看下这个算法.在我们的朴素匹配模式算法中我们会发现做了无用功,比如我们在字符串A"abcdabdac"中查找字符串B''abd".按照逻辑,我们是从头到尾进行字符串A和B的比较

Untitled.png

当我们发现字符串B中的字符'd'和字符串的字符'c'不相同时,我们分别把字符串B和字符串A的字符'b'对齐,再重新进行比较:

Untitled.png

,一直这样位移到最后,找到匹配字符串或者没有匹配字符串为止:

Untitled.png

不用想要是字符串的长度很长的时候这种算法耗时是我们绝对不能忍受的.

通过观察,我们要是人工匹配的话我们会,如当我们第一次匹配的时候可以直接把字符串B移动到这里,而字符串A则不回溯回去了.

Untitled.png

而这也是kmp匹配算法的思想.只是计算机怎么知道该回溯到哪里呢?那我们就鼓捣一个回溯表呗,于是kmp算法就有了一个next值,记录该回溯到哪里,而这个也是kmp匹配算法的精髓.

google很久,发现很多博客和书籍包括大话上说,next求值遵循这么一个原则:

当j=0时,next[j]=-1
Max{k|1<k<j,且'p1....pk-1'==pj-k+1...pj-1'}当此集合不空时
其它情况,next[j]=0

不知道别人看到有没有看懂,反正我看到第二个规则时是懵的,啥玩意儿呢这是...当然,接着<<大话>>上面的例子也很清晰,我也明白了原则2是个什么东西,发现这厮跟最大子序列求和差不多,当然也有区别,其实就是这么个意思,在长度为y的字符串B中存在一个下标k是的B(1)-B(k-1)的值和B(k+1)到B(y-1)的值是相同的.然后next[j]的值就为k,然后经过最牛逼的优化后就有了这么一段我思考了很久都没有搞懂的超级经典代码,即

void GetNext(int StringB[],int *Next)
{
    int MainStringPosition,NextBack;

    NextBack=-1;
    StringLength=strlen(StringB);

    while(MainStringPosition<StringLength-1)
    {
        if(NextBack==-1||StringB[NextBack]==StringBack[MainStringPosition])
        {
            NextBack++;
            MainStringPosition++;
            Next[MainStringPosition]=NextBack;
        }
        else
            NextBack=Next[NextBack];
    }
}

当然是看不懂这段代码的,这可是经过N个前辈们优化过的代码呢.google后看到有些博客说:这啊,就是一个推导过程,什么Next[k+1]=Next[k]+1之类,不过都是一笔带过,让人更加迷惑.还好,看到这篇博客对next的推导过程,顿时豁然开朗(链接:http://www.cnblogs.com/yjiyjige/p/3263858.html#commentform).原理我已经,其实就是next[j]的值为k,而这个k满足这么一个条件,即StringB[0]-StringB[k-1]的值和StringB[k+1]-StringB[length-1]的字符串相同(除去j=0的情况)

这里补上这篇博客对其next推导的过程:

现在要始终记住一点，next[j]的值（也就是k）表示，当P[j] != T[i]时，j指针的下一步移动位置。

先来看第一个：当j为0时，如果这时候不匹配，怎么办？

1.png

像上图这种情况，j已经在最左边了，不可能再移动了，这时候要应该是i指针后移。所以在代码中才会有next[0] = -1;这个初始化。

如果是当j为1的时候呢？

2.png

显然，j指针一定是后移到0位置的。因为它前面也就只有这一个位置了~~~

下面这个是最重要的，请看如下图：

3.png4.png

请仔细对比这两个图。

我们发现一个规律：

当P[k] == P[j]时，

有next[j+1] == next[j] + 1

其实这个是可以证明的：

因为在P[j]之前已经有P[0 ~ k-1] == p[j-k ~ j-1]。（next[j] == k）

这时候现有P[k] == P[j]，我们是不是可以得到P[0 ~ k-1] + P[k] == p[j-k ~ j-1] + P[j]。

即：P[0 ~ k] == P[j-k ~ j]，即next[j+1] == k + 1 == next[j] + 1。

这里的公式不是很好懂，还是看图会容易理解些。

那如果P[k] != P[j]呢？比如下图所示：

5.png

像这种情况，如果你从代码上看应该是这一句：k = next[k];为什么是这样子？你看下面应该就明白了。

6.png

现在你应该知道为什么要k = next[k]了吧！像上边的例子，我们已经不可能找到[ A，B，A，B ]这个最长的后缀串了，但我们还是可能找到[ A，B ]、[ B ]这样的前缀串的。所以这个过程像不像在定位[ A，B，A，C ]这个串，当C和主串不一样了（也就是k位置不一样了），那当然是把指针移动到next[k]啦。

看了上面的推导过程肯定就豁然开朗了.嘿嘿,我也是,这里感谢这个博主

知道了next[]的推导过程,写kmp算法也就不难了不是,嘿嘿...

BOOL KMPString(int MainString[],int PatternString[],int StartFindPosition,int *FindPosition)//MainString代表主串,PatternString代表字串,StartFindPosition代表开始匹配的位置,FindPosition代表找到字符串的匹配位置
{
    int PatternNext==-1;
    int *Next;

    if(!Next=(int*)malloc(sizeof(int)*strlen(PatternString)))
        return flase;
    GetNext(PatternString,Next);
    if(Position>strlen(MainStringp[]))
        return false;//如果开始匹配的位置不在主串范围,返回false
    
    while(Position<strlen(MainString[]))
    {
        if(MainString[Postion]==PatternString[PatternNext]||PatternNext==1-)//当前的字符串匹配,后移一位继续匹配
        {
             PatternNext++;
             MainString++;
        }
        else
            PatternNext=Next(PatternNext);//当前字符串不匹配,字串回溯到相应位置进行下一次比对
    }
    if(PatternNext>strlen(PatternString))//如果找到相同字符串
        FindPosition=Position-strlen(PatternString);
    else//未找到则返回-1表示无值相同
        FindPosition=-1;
    return true;
}

不过我们也发现了一个kmp这厮的弱点,比如主串为aaaabcdef,字串为aaaaax,那么按照kmp匹配就是下图这样:

IMG_20140329_102841.jpg

图中我的笔记也写了,2,3,4,5步骤是多余的,所以我们改造下这厮,也就是下面的代码:

void NewGetNext(int StringB[],int *Next)
{
    int MainStringPosition,NextBack;

    NextBack=-1;
    StringLength=strlen(StringB);

    while(MainStringPosition<StringLength-1)
    {
        if(NextBack==-1||StringB[NextBack]==StringBack[MainStringPosition])
        {
            NextBack++;
            MainStringPosition++;
            if(StringB[NextBack]==StringB[MainStringPosition]//这个判断是新增的,判断当前的值是否和前一个相同,如果是相同的话,那么这里的回溯就和前一个位置的回溯是相同的,也就是上面例子中直接跳过了2,3,4,5步匹配步骤
                Next[MainStringPosition]=Next(NextBack);
            else
                Next[MainStringPosition]=NextBack;
                
        }
        else
            NextBack=Next[NextBack];
    }
}

好了,kmp匹配算法就搞定了,其实周二就顿悟了的,不过又接着研究了下BM算法,感觉更加不错,嘿嘿,待会再写这个BM算法

- 写于