kmp算法--通俗易懂-蒲公英云

今天花了好几个小时学习这个算法，担心之后忘记，所以在这里做些总结。也方便其它人学习借鉴。

学习理解的过程中也看了很多帖子，但感觉说的都不是特别清楚，也对照了课本，但是大量的推理证明并不到好理解，没有与程序结合起来讲，明明已经明白的原理在教材中还要费力理解。所以文末我会推荐一篇写的特别好的博文，希望能帮到大家。

正文：

1. kpm算法的原理

本部分内容转自：http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt\_algorithm.html

举例来说，有一个字符串（主串）”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串（模式串）”ABCDABD”？

许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。

这种算法不太容易理解，网上有很多解释，但读起来都很费劲。直到读到Jake Boxer的文章，我才真正理解这种算法。下面，我用自己的语言，试图写一篇比较好懂的KMP算法解释。

首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。

因为B与A不匹配，搜索词再往后移。

就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

接着比较字符串和搜索词的下一个字符，还是相同。

直到字符串有一个字符，与搜索词对应的字符不相同为止。

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把”搜索位置”移到已经比较过的位置，重比一遍。

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此如果把搜索词放到一个一维数组P[]中，（我也看过许多其它的帖子，他们一维数组有的是从0开始，有的是从1开始，误导了我好久，最后我会把两种代码都列出来，大家可以对比学习，这也是我的一个弱点，咱们这里按照从0开始，后边求next数组是为了对照方便，也会从0开始）应该主串不移动，恰巧搜索词移动到P[2]位置上继续进行匹配

10.

因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。于是将搜索词移动到P[0]位置上。

11.

因为空格与A不匹配，没有已匹配的字符，继续后移一位。//j=next[j-1],j不能等于0

12.

逐位比较，直到发现C与D不匹配。于是继续从搜索词中的P[2]开始匹配。

13.2

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），再从搜索词的P[0]开始匹配，这里就不再重复了。

14.

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。

15.

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

　　－　“A”的前缀和后缀都为空集，共有元素的长度为0；

　　－　“AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；

　　－　“ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

　　－　“ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

　　－　“ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；

　　－　“ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；

　　－　“ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

16.

“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。

2.next数组的求解思路与后续优化（这里我就不做过多的赘述，我们就一步到位，在求解next数组的同时一步到位，进行优化）

char p[8]="ABCDABD";
int next[7]={0};
void makenext(const char p[],int next[])//注意这里的const，与strlen函数有关
{
    int j,k=0;//模板字符串下标j，最大前后缀长度
    int m=strlen(p);//模板字符串长度
    next[0]=0;//模板字符串的第一个字符的最大前后缀长度为0
    for(j=1,k=0;j<m;j++)
        {
            while(k>0&&p[k]!=p[j]) k=next[k-1];//k>0保证next[k-1]有意义
            if(p[k]==p[j]) k++;//看下图解释
                next[j]=k;
             }
}

如果蓝色的部分相同即p[k]==p[j]，则当前 next 数组的值为上一个 next 的值加一，如果不相同，就是我们下面要说的！

如果不相同，用一句话来说，就是：

从前面来找子前后缀

1如果要存在对称性，那么对称程度肯定比前面这个的对称程度小，所以要找个更小的对称，这个不用解释了吧，如果大那么就继承前面的对称性了。

2要找更小的对称，必然在对称内部还存在子对称，而且这个必须紧接着在子对称之后。

如果看不懂，那么看一下图吧！

正文结束，下面来看代码：

模式串数组从1开始：

p[1]………p[k] p[k+1] ………….. p[j-k]……..p[j-1]p[j]

模式串数组从0开始：

p[0]………p[k-1] p[k] ………… p[j-k]……..p[j-1] p[j]

//该代码从0开始
<span style="color: rgb(51, 51, 51); font-family: monospace; white-space: pre; background-color: rgb(240, 240, 240);">  #include <iostream></span>
#include <string>
using namespace std;
void makenext(const char p[],int next[])//注意这里的const，与strlen函数有关
{
    int j,k=0;//模板字符串下标j，最大前后缀长度
    int m=strlen(p);//模板字符串长度
    next[0]=0;//模板字符串的第一个字符的最大前后缀长度为0
    for(j=1,k=0;j<m;j++)
        {
            while(k>0&&p[k]!=p[j]) k=next[k-1];//k>0保证next[k-1]有意义
            if(p[k]==p[j]) k++;//如果前后
            next[j]=k;
         }
}
int kmp(char s[],char p[],int next[],int pos)
{
    int n=strlen(s);//主串s的长度
    int m=strlen(p);//模式串p的长度
    makenext(p,next);
    for(int i=pos,j=0;i<n;i++)
    {
        if(j>0&&p[j]!=s[i]) j=next[j-1];
        if(p[j]==s[i]) j++;//在这里如果最后一个字符也相等，仍j++
        if(j==m)  return i-m+1;//（这里修改后可以找出主串中所有符合条件的位置）
    }
}
int main()
{
    char s[]="ababxbababcdabddsss";
    char p[8]="abcdabd";
    int next[7]={0};
    int pos;//从主串的pos位置起
    cin>>pos;
    cout<<kmp(s,p,next,pos);
    return 0;
}