kmp算法--通俗易懂

心已赠人 2022-07-15 18:38 310阅读 0赞

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

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

**正文：**

**1. kpm算法的原理**

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

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

**![bg2013050101.jpg][]**

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

**![bg2013050102.jpg][]**

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

**1.**

**![bg2013050103.png][]**

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

**2.**

**![bg2013050104.png][]**

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

**3.**

**![bg2013050105.png][]**

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

**4.**

**![bg2013050106.png][]**

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

**5.**

**![bg2013050107.png][]**

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

**6.**

**![bg2013050108.png][]**

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

**7.**

**![bg2013050107.png][]**

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

**8.**

**![bg2013050109.png][]**

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

**9.**

**![bg2013050107.png][]**

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

**10.**

**![bg2013050110.png][]**

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

**11.**

**![bg2013050111.png][]**

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

**12.**

**![bg2013050112.png][]**

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

**13.2**

**![bg2013050113.png][]**

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

**14.**

**![bg2013050114.png][]**

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

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

**15.**

**![bg2013050109.png][]**

**"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"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.**

**![bg2013050112.png][]**

**"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"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 的值加一，如果不相同，就是我们下面要说的！**

**![umuea2.jpg_web][]**

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

**从前面来找子前后缀**

**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;
    }

写博文还挺花时间 的，这篇博文用了3个多小时。。。

[bg2013050101.jpg]: http://image.beekka.com/blog/201305/bg2013050101.jpg
[Knuth-Morris-Pratt]: http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
[bg2013050102.jpg]: http://image.beekka.com/blog/201305/bg2013050102.jpg
[Link 1]: http://www.google.com/search?q=Knuth-Morris-Pratt+algorithm
[Jake Boxer]: http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
[bg2013050103.png]: http://image.beekka.com/blog/201305/bg2013050103.png
[bg2013050104.png]: http://image.beekka.com/blog/201305/bg2013050104.png
[bg2013050105.png]: http://image.beekka.com/blog/201305/bg2013050105.png
[bg2013050106.png]: http://image.beekka.com/blog/201305/bg2013050106.png
[bg2013050107.png]: http://image.beekka.com/blog/201305/bg2013050107.png
[bg2013050108.png]: http://image.beekka.com/blog/201305/bg2013050108.png
[bg2013050109.png]: http://image.beekka.com/blog/201305/bg2013050109.png
[bg2013050110.png]: http://image.beekka.com/blog/201305/bg2013050110.png
[bg2013050111.png]: http://image.beekka.com/blog/201305/bg2013050111.png
[bg2013050112.png]: http://image.beekka.com/blog/201305/bg2013050112.png
[bg2013050113.png]: http://image.beekka.com/blog/201305/bg2013050113.png
[bg2013050114.png]: http://image.beekka.com/blog/201305/bg2013050114.png
[umuea2.jpg_web]: http://img1.tuicool.com/umuea2.jpg!web