KMP浅显理解

本是古典何须时尚 2022-04-11 10:46 175阅读 0赞

# KMP算法解释 #

## 1.好的博客 ##

[从头到尾彻底理解KMP算法][KMP]，这是我在搜索各种博客之后，解释的最为详尽的一篇关于介绍KMP算法的一篇博客。自己的理解也算是建立在这篇博客上。很早很早之前就已经学过了，不过还是忘了好多。现在再拾起来按照自己的理解疏解一遍。

## 2.KMP缘何而起 ##

目标问题，给你一个文本串S,文本串T求出S中与T相匹配的第一个位置。  
我们有朴素的算法是：

int j=1;
    int i=1;
    int s0=strlen(S);
    int tp=strlen(T);
    while(i<=s0&&j<=t0)
    {
    		if(S[i]==T[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			i++;
    			j=1;
    		}
    }

这是最为简单的暴力算法，同时我们也会发现，每一次匹配不成功的时候我们都会要去从头开始匹配。

如上图所示当abc与abb失配的时候我们会将a再与b去匹配，但是实际上我们早已经知道了第二个字符是b。所以如此显而效率会较为低下.

## 3.KMP算法解释 ##

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。

--------------------

简要思路:当我们匹配到S字符串中的第i个位置的时候，此时匹配到T字符串的第j个字符，此时有i-j+1位置到i位置与T字符串中的字符相匹配。

> 如果第j+1个字符相匹配，接着向下进行匹配即可。  
> 如果第j+1个字符失配，我们就控制S中字符位置不发生改变，将T向后滑动一段位置。(next\[j\])

我们先来看KMP算法的代码

int j=0;
    int s0=strlen(S);
    int t0=strlrn(T);
    while(i<s0&&j<t0)
    {
    	if(j==0||S[i]==T[j])
    	{
    		i++;
    		j++;
    	}
    	else
    	{
    		j=next[j];
    	}
    	if(j>t0)
    	return i-t0;
    	else
    	 return 0;
    }

--------------------

代码中next即为向右滑动的值。那么如何去理解这个next值则成了关键，自己也被折磨了好久好久。

int j=0;
    	int i=1;
    	next[1]=0;
    	int t0=strlen(T);
    	while(i<t0)
    	{
    		if(j==0||T[j]==T[j])
    		{
    			i++;
    			j++;
    			next[i]=j;
    		}
    		else
    		{
    			j=next[j];
    		}
    	}

理解如下

--------------------

--------------------

在这里j所表示的含义代表着第j个字符位置前面与T字符串从头开始最大匹配长度。拿上面表格举例来说，在最后一个位置我们发生了失配问题，D之前与字符串T从头匹配最大长度为2,截至到C为止。所以我们就将字符串的位置滑到了C处。 **next的值所表示的东西就是j处字符前面的字符与T字符串从头开始匹配的最大长度!!!**

但其实截至到现在这个算法还不算完美，因为我们还会有一种极特殊的情况。

比如上面表格所列处的这种结构当B失配的时候我们右移到了左边的A的位置，A失配后我们右移到了第四个A的位置，但显然我们之前已经知道了肯定会失配的结果。

--------------------

b失配移到了第二个位置但这个时候还是b，所以所得结果依然会是失配，明知故作？

实际上是我们求next的过程中有点小疏漏，这个时候应该要能够满足如果j==T\[next\[j\]\]那么j=next\[next\[j\]\],因为如果T\[j\]=T\[next\[j\]\]则肯定失配，则应该尽量避免这种状况。

--------------------

int j=0;
    int i=1;
    int t0=strlen(T);
    while(i<=t0)
    {
    	if(j==0||T[j]==T[i})
    	{
    		i++;
    		j++;
    		if(T[i]!=T[j])
    		next[i]=j;
    		else
    		{
    			next[i]=next[j];
    		}
    	}
    	else
    	{
    		j=next[j];
    	}
    }

--------------------

自己目前也理解的不是特别充分，也只能将自己想出来的，大概写出来成这个样子了，实在理解不了的话可以采取强制记忆措施，只不过实在不是太好的样子。  
up！up！

[KMP]: https://blog.csdn.net/v_july_v/article/details/7041827