`
hm4123660
  • 浏览: 282437 次
  • 性别: Icon_minigender_1
  • 来自: 广州
博客专栏
Dea4ce76-f328-3ab2-b24a-fb268e1eeb75
数据结构
浏览量:69994
社区版块
存档分类
最新评论

KMP算法详解

阅读更多

     字符串模式匹配我们相信大家都有遇过,然而我们也习惯用简单匹配法(即Brute-Force算法),其基本思路就是一个个逐一对比下去,这也是我们大家熟知的方法,然而这种算法的效率并不高,但利于理解。

 

    假设主串s="ababcabcacbab",模式串为t="abcac",我们用肉眼很容易看出匹配位置为是s[5]--s[10];利用简单匹配算法代码如下:

int BF(string s,string t)//Brute-Force,简单匹配算法
{
	int origin=-1;//模式匹配的起始位置
	for(int i=0;i<s.size();i++)
	{
		int k;
		for(k=0;k<t.size();k++)
		{
			if(s[i+k]!=t[k])
			   break;
		}
		if(k==t.size())//匹配成功
		{
			origin=i;
			break;
		}
	}
	return origin;//返回匹配成功的位置,若为-1,则匹配失败
}

 然后这种算法效率显而易见效率并不高,其中包含了过多的不必要操作,并不能很好地达到实际工作中需要的效率。这种算法在最好的情况下时间复杂度为O(m),在最坏的情况下时间复杂度为M(nm)。

 

KMP算法

   KMP算法较Brute-Force算法有较大的改进,主要消除了主串指针的回溯,从而是算法的效率有了某种程度的提高。

 

    为了消除主串的指针回溯,需要分析模式串t,我们利用next[]数组来记录存放这些“部分匹配信息”。

next[]计算规则如下:

1)next[j]=-1;  j=0;

2)  next[j]=max(k);    0<k<j,p[0....k-1]=p[j-k...j-1];

3)  next[j]=0;   其他条件

 

例如:计算ababa的next[]数组值

按照上面的规则我们可以填写出下表的next[]数组

p a b a b a
j 0 1 2 3 4
next[j] -1 0 0 1 2

 

根据上面规则,当j=0,next[j]=-1,所以第一个a的next值为-1;

 

当j=1时,0<k<j这样的k不存在,所以属于其他条件,即为0;

 

当j=4时,0<k<j,这样的k=1,2,3,因为要求最大的K,即从大到小验证k是否满足p[0....k-1]=p[j-k...j-1],若一个都不满足,属于其他条件,即为0,

当k=3时,str1=p[0....k-1]=aba,str2=p[j-k...j-1]=bab,str1!=str2,所以k!=3;

当k=2时,str1=p[0....k-1]=ab,str2=p[j-k...j-1]=ab,str1==str2,满足条件,所以k=2;

 

根据上面的条件,可以轻易写出next的计算函数;

//计算next数组,t为计算字符串
void calculateNext(int * & next,string t)
{
	for(int j=0;j<t.size();j++)
	{
		bool state=true;//是否是等于0的情况
		if(j==0)
			*next=-1;
		else 
		{
			int k=j-1;//0<k<j,获取最大的k
			while(k>0)
			{
				string str1="",str2="";
				for(int i=0;i<=k-1;i++)
				{
					str1=str1+t[i];
					str2=str2+t[j-k+i];
				}
				if(str1==str2)//若,p[0....k-1]=p[j-k...j-1];
				{	
					*(next+j)=k;
					state=false;//不是等于0的情况
					break;
				}
				k--;
				
			}
			if(state)  //满足其他条件,即为0
		          *(next+j)=0;
		}

	}
}

 

计算出匹配信息next后,我们就可以进行KMP匹配了,

主要思路是:

假设i和j分别为指示主串和模式串中正在比较的字符的当前位置,并对i 和j 赋初值0。
在匹配的过程中,若si=tj,则i和j分别增加1,继续进行比较。
否则,若j=0,si!=tj,则从s的下一个字符开始,即i增加一,若j!=0,令j=next[j]

 

理解了上面的思路,就很容易编写出KMP匹配代码:

//kmp匹配算法,s为主串,t为模式串
int KMP(int * next,string s,string t)
{
	int j=0,i=0;//i为主串s正在匹配的字符,j为t正在匹配的字符
	
	while(i<s.size()&&j<t.size())
    {
        if(t[j] == s[i])
        {
            j++;i++;
        }
        else
        {
            if(j==0) 
            {
                i++;//若第一个字符就匹配失败,则从s的下一个字符开始
            }
            else
            {
				
                j = *(next+j);//,也可以j=next[j],用next确定t应回溯到的字符
            }
        }
    }
    if(j < t.size())//整个过程匹配失败
    {
        return -1;
    }
    return i-t.size();//匹配成功
	//第二种写法
	/*2. while(i < s.size())  
         {  
                  while(j > -1 && t[j] != s[i])  
                          j = next[j];  
                  i++, j++;  
                  if(j >= t.size()) return i - j;  
         }  
	 return -1;  */


	
}

 

至此,我们就完成了KMP算法的学习。在学习KMP过程中,我发了一篇“另一种”有关的KMP算法,更好理解学习,附上链接:http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

 

本次KMP的源代码地址:https://github.com/longpo/algorithm

2
0
分享到:
评论

相关推荐

    KMP算法详解KMP算法详解

    KMP 算法详解 KMP 算法是字符串模式匹配的一种高效算法,解决了字符串中模式匹配的问题。该算法可以在 O(m+n) 的时间复杂度内完成字符串模式匹配。 简单匹配算法 简单匹配算法的思想是直截了当的,将主串 S 中...

    KMP算法详解 KMP算法详解

    KMP算法详解 KMP算法详解 KMP算法详解

    kmp算法详解及练习

    ### KMP算法详解 #### 一、KMP算法概述 KMP算法,全称为Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,由Donald Knuth、James H. Morris和Vaughan Pratt三位计算机科学家共同提出。该算法主要用于解决在主...

    kmp算法详解

    "kmp算法详解" KMP 字符串模式匹配算法是高效的字符串匹配算法,时间复杂度为 O(m+n),其中 m 和 n 分别是主串和模式串的长度。KMP 算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。 KMP 算法的...

    关于数据结构中的kmp算法详解

    ### KMP算法详解:原理与应用 #### 引言 KMP算法,全称为Knuth-Morris-Pratt算法,是一种高效的字符串匹配算法,由Donald E. Knuth、James H. Morris以及Vaughan Pratt三位计算机科学家共同提出。相较于传统的模式...

    模式匹配的KMP算法详解.

    ### 模式匹配的KMP算法详解 #### 一、KMP算法背景及传统模式匹配算法 KMP算法,即Knuth-Morris-Pratt算法,是由Donald E. Knuth、James H. Morris和Vaughan R. Pratt三位计算机科学家在1977年共同提出的一种高效的...

    严蔚敏数据结构kmp算法详解PPT学习教案.pptx

    严蔚敏数据结构kmp算法详解PPT学习教案.pptx 本资源摘要信息将对严蔚敏数据结构kmp算法的学习教案进行详细的讲解和分析。KMP算法是字符串匹配算法中的一种重要算法,它可以高效地进行字符串匹配。 首先,我们需要...

    字符串模式匹配KMP算法详解.doc

    ### 字符串模式匹配KMP算法详解 #### 一、引言 在计算机科学领域,字符串模式匹配是一项基本且重要的任务。它涉及到在一个较大的文本字符串(通常称为“主串”或“目标串”)中寻找一个较小的字符串(称为“模式串...

    严蔚敏-数据结构-kmp算法详解.ppt

    严蔚敏-数据结构-kmp算法详解.ppt该文档详细且完整,值得借鉴下载使用,欢迎下载使用,有问题可以第一时间联系作者~

    KMP算法详解-彻底清楚了.pdf

    《KMP算法详解》 KMP(Knuth-Morris-Pratt)算法是一种在字符串中查找子串出现位置的高效算法,由Donald Knuth、James H. Morris和 Vaughan Pratt共同提出。该算法避免了在匹配过程中对已匹配部分的重新比较,显著...

    KMP算法详解.doc

    "KMP算法详解" 一、KMP字符串模式匹配算法 KMP字符串模式匹配算法是一种高效的字符串模式匹配算法,能够在一个字符串中快速地定位另一个字符串。该算法的时间复杂度为O(m+n),远远优于简单匹配算法的时间复杂度O(m...

    KMP算法详解.mhtml

    KMP算法详解.mhtml

    模式匹配的KMP算法详解

    【KMP算法详解】 KMP(Knuth-Morris-Pratt)算法是一种高效地进行字符串模式匹配的算法,由D.E.Knuth、J.H.Morris和V.R.Pratt三位学者独立提出。它解决了在主串(S)中查找模式串(T)出现的位置问题,避免了在匹配...

    KMP、Mancher和扩展KMP算法详解

    KMP、Mancher和扩展KMP算法详解,但是其中的参考代码有一点小错误,请自行参考网络

    KMP算法详解够详细了

    相比于简单的暴力匹配算法,KMP算法显著提高了性能,避免了不必要的字符回溯。它的核心在于构造一个模式函数next,也称为部分匹配表,用于存储模式串中每个位置的最长前缀和后缀的公共长度。 简单匹配算法,也称为...

    【基础】KMP算法详解.pdf

    本文介绍了KMP算法的原理和基本实现方法,附带算法模板的代码和详解。如想了解更多内容,欢迎关注微信公众号:信息学竞赛从入门到巅峰。

    KMP算法详解0.0.doc

    KMP算法的核心在于构建一个称为“部分匹配表”或“next数组”,用于存储模式串中每个位置的前缀和后缀的最大公共长度。 在构建next数组的过程中,我们需要遵循以下两个条件: 1. 当比较到某个位置时,如果模式串的...

Global site tag (gtag.js) - Google Analytics