精华内容
下载资源
问答
  • 4.3.2 KMP 算法 KMP 算法是 D.E.Knuth J.H.Morris 和 V .R.Pratt 共同提出的 , 简称 KMP 算法算法较 BF 算法有较 大改进 , 主要是消除了主串指针的回溯 , 从而使算法效 率有了某种程度的提高 所谓 真子串 是指模式...
  • 学了两天的KMP算法,总算有了自己的一点理解,写在这里做个记录了,也与各位大神交流,期待大神的指正! AC代码: #include <iostream> #include <cstring> using namespace std; #define MaxSize ...

    学了两天的KMP算法,总算有了自己的一点理解,写在这里做个记录了,也与各位大神交流,期待大神的指正!
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    AC代码:

    #include <iostream>
    #include <cstring>
    using namespace std;
    #define MaxSize 255    // 串的最大长度
    
    // 串的定长顺序存储结构
    typedef struct
    {
        char ch[MaxSize+1]; // 存储串的一维数组
        int length;   // 串的当前长度
    }SString;
    
    // 初始化
    void Init(SString &S, char s[])
    {
        S.length = strlen(s);
        for(int i = 1; i < S.length+1; i++)
        {
            S.ch[i] = s[i-1];
        }
        S.ch[0] = S.length;
    }
    /*
    // 通过计算返回字串T的next数组值
    void get_next(String T, int *next)
    {
        int i, j;
        i = 1; j = 0;
        next[1] = 0;
        while (i<T.ch[0])  // 此时T[0]表示串T的长度
        {
            if(j == 0 || T.ch[i] == T.ch[j]) // T[i]表示后缀的单个字符, T[j]表示前缀的单个字符
            {
                ++i;
                ++j;
                next[i] = j;
            }
            else
                j = next[j];  // 若字符不相同,则 j 值回溯
        }
    }
    */
    // 求模式串T的next数组修正值并存入nextval数组
    void get_nextval(SString T, int nextval[ ])
    {
        int i , j;
        i = 1; j = 0;
        nextval[1] = 0;
        while (i < T.ch[0])   // 此处T[0]表示串T的长度
        {
            if(j == 0 || T.ch[i] == T.ch[j])  // T[i]表示后缀的单个字符,T[j]表示前缀的单个字符
            {
                ++i;
                ++j;
                if(T.ch[i] != T.ch[j])  // 若当前字符与前缀字符不同
                    nextval[i] = j;  // 则当前的 j 为nextval 在 i 位置的值
                else
                    nextval[i] = nextval[j]; // 如果当前字符与前缀字符相同,
                                                         // 则将前缀字符的nextval 值赋值给nextval在位置 i  的值
            }
            else
                j = nextval[j]; // 若字符不相同,则 j 值回溯
        }
    }
    
    // 返回字串T在主串S中第pos 个字符之后的位置。若不存在,则返回0;
    // T非空,1<=pos<=StrLength(S);
    int Index_KMP(SString S, SString T, int pos)
    {
        int i = pos; // i 用于表示主串S当前下标值,若pos不为1,则从pos位置开始匹配
        int j = 1;  // j 用于表示字串T当前下标值
        int nextval[255]; // 定义一next数组
        get_nextval(T, nextval); // 对串T进行分析,得到nextval数组
        while(i <= S.ch[0] && j <= T.ch[0]) // 当 i 小于S的长度且 j 小于T的长度时,循环继续
        {
            if(j == 0 || S.ch[i] == T.ch[j]) // 两字符相等则继续,与朴素算法增加了 j=0 的判断
            {
                ++i;
                ++j;
            }
            else        // 指针 j 后退,重新开始匹配
            {
                j = nextval[j];   // j 退回合适的位置,i 值不变
            }
        }
        if(j > T.ch[0])
        {
            cout<<i - T.ch[0]<<endl;
            return i - T.ch[0];
        }
        else
        {
            cout<<"匹配失败!"<<endl;
            return 0;
        }
    }
    int main()
    {
        SString S; SString T; int pos;
        char s[MaxSize+1], t[MaxSize+1];
        cout<<"请输入主串S:"<<endl;
        cin>>s;
        Init(S, s);
        cout<<"请输入模式串T:"<<endl;
        cin>>t;
        Init(T, t);
        cout<<"请输入你想要在S中开始匹配的位置 pos:"<<endl;
        cin>>pos;
        cout<<"匹配结果:";
        Index_KMP(S, T, pos);
        return 0;
    }
    
    展开全文
  • 数据结构KMP算法配图详解(超详细)

    万次阅读 多人点赞 2020-02-18 22:02:42
    KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练,但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂...

    KMP算法配图详解

    前言

    KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练,但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂,很多正规的书本把概念一摆出直接劝退无数人。这篇文章将尽量以最详细的方式配图介绍KMP算法及其改进。文章的开始我先对KMP算法的三位创始人Knuth,Morris,Pratt致敬,懂得这个算法的流程后你真的不得不佩服他们的聪明才智。

    KMP解决的问题类型

    KMP算法的作用是在一个已知字符串中查找子串的位置,也叫做串的模式匹配。比如主串s=“goodgoogle”,子串t=“google”。现在我们要找到子串t 在主串s 中的位置。大家肯定觉得这还不简单,不就在第五个嘛,一眼就看出来了。
    当然,在字符串非常少时,“肉眼观察法”不失为一个好方法。但如果要你在一千行文本里找一个单词,我想一般人都会数得崩溃吧。这就让我想起来考试的时候,如果一两道选择题不会。这时候,“肉眼观察法”可能效果不错,但是如果好几道大题不会呢?“肉眼观察法”就丝毫不起效了。所以打铁还需自身硬,我们把这种枯燥的事以一定的算法交给计算机处理。
    第一种我们容易想到的就是暴力求解法。
    这种方法也叫朴素的模式匹配

    简单来说就是:从主串s 和子串t 的第一个字符开始,将两字符串的字符一一比对,如果出现某个字符不匹配,主串回溯到第二个字符,子串回溯到第一个字符再进行一一比对。如果出现某个字符不匹配,主串回溯到第三个字符,子串回溯到第一个字符再进行一一比对…一直到子串字符全部匹配成功。

    下面我们通过图片展示这个过程:
    竖直线表示相等,闪电线表示不等
    第一个过程:子串“goo”部分与主串相等,'g’不等,结束比对,进行回溯。
    在这里插入图片描述
    第二个过程:开始时就不匹配,直接回溯
    在这里插入图片描述
    第三个过程:开始时即不匹配,直接回溯
    在这里插入图片描述
    第四个过程:开始时即不匹配,直接回溯
    在这里插入图片描述
    第五个过程:匹配成功
    在这里插入图片描述
    大家可能会想:这个方法也太慢了吧!求一个子串位置需要太多的步骤。而且很多步骤根本不必要进行。
    这个想法非常好!!很多伟大的思想都是在一步步完善更正已有方法中诞生的。这种算法在最好情况下时间复杂度为O(n)。即子串的n个字符正好等于主串的前n个字符,而最坏的情况下时间复杂度为O(m*n)。相比而言这种算法空间复杂度为O(1),即不消耗空间而消耗时间。

    下面就开始进入我们的正题:KMP算法是怎样优化这些步骤的。其实KMP的主要思想是:“空间换时间”。
    大家打起精神,认真看下面的内容
    首先,为什么朴素的模式匹配这么慢呢?
    你再回头看一遍就会发现,哦,原来是回溯的步骤太多了。所以我们应该尽量减少回溯的次数。
    怎样做呢?比如上面第一个图:当字符’d’与’g’不匹配,我们保持主串的指向不变,
    主串依然指向’d’,而把子串进行回溯,让’d’与子串中’g’之前的字符再进行比对。
    如果字符匹配,则主串和子串字符同时右移。
    至于子串回溯到哪个字符,这个问题我们先放一放。

    我先提出一个概念:一个字符串最长相等前缀和后缀。
    教科书常用的手段是:在此处摆出一堆数学公式让大家自行理解。
    在这里插入图片描述
    这也是为什么看计算机学科的书没有较好的数学基础会很痛苦。(当初我为什么不好好学数学T_T)
    大家先不要强行理解数学公式,且听我慢慢道来:
    我给大家个例子。
    字符串 abcdab
    前缀的集合:{a,ab,abc,abcd,abcda}
    后缀的集合:{b,ab,dab,cdab,bcdab}
    那么最长相等前后缀不就是ab嘛.

    做个小练习吧:
    字符串:abcabfabcab中最长相等前后缀是什么呢:
    对就是abcab
    好了我们现在会求一个字符串的前缀,后缀以及最长相等前后缀了。
    这个概念很重要。到这里如果都看懂了,可以鼓励一下自己,然后回想一遍,再往下看。
    之前留了一个问题,子串回溯到哪个字符,现在可以着手解决了。

    图解KMP

    现在我们先看一个图:第一个长条代表主串,第二个长条代表子串。红色部分代表两串中已匹配的部分,
    绿色和蓝色部分分别代表主串和子串中不匹配的字符。
    再具体一些:这个图代表主串"abcabeabcabcmn"和子串"abcabcmn"。
    在这里插入图片描述
    在这里插入图片描述
    现在发现了不匹配的地方,根据KMP的思想我们要将子串向后移动,现在解决要移动多少的问题。
    之前提到的最长相等前后缀的概念有用处了。因为红色部分也会有最长相等前后缀。如下图:
    在这里插入图片描述
    在这里插入图片描述
    灰色部分就是红色部分字符串的最长相等前后缀,我们子串移动的结果就是让子串的红色部分最长相等前缀和主串红色部分最长相等后缀对齐。
    在这里插入图片描述
    在这里插入图片描述
    这一步弄懂了,KMP算法的精髓就差不多掌握了。接下来的流程就是一个循环过程了。事实上,每一个字符前的字符串都有最长相等前后缀,而且最长相等前后缀的长度是我们移位的关键,所以我们单独用一个next数组存储子串的最长相等前后缀的长度。而且next数组的数值只与子串本身有关。
    所以next[i]=j,含义是:下标为i 的字符前的字符串最长相等前后缀的长度为j。
    我们可以算出,子串t= "abcabcmn"的next数组为next[0]=-1(前面没有字符串单独处理)
    next[1]=0;next[2]=0;next[3]=0;next[4]=1;next[5]=2;next[6]=3;next[7]=0;

    abcabcmn
    next[0]next[1]next[2]next[3]next[4]next[5]next[6]next[7]
    -10001230

    本例中的蓝色c处出现了不匹配(是s[5]!=t[5]),
    在这里插入图片描述
    我们把子串移动,也就是让s[5]与t[5]前面字符串的最长相等前缀后一个字符再比较,而该字符的位置就是t[?],很明显这里的?是2,就是不匹配的字符前的字符串 最长相等前后缀的长度。
    在这里插入图片描述
    也是不匹配的字符处的next数组next[5]应该保存的值,也是子串回溯后应该对应的字符的下标。 所以?=next[5]=2。接下来就是比对是s[5]和t[next[5]]的字符。这里也是最奇妙的地方,也是为什么KMP算法的代码可以那么简洁优雅的关键。
    我们可以总结一下,next数组作用有两个:
    一是之前提到的,

    next[i]的值表示下标为i的字符前的字符串最长相等前后缀的长度。

    二是:

    表示该处字符不匹配时应该回溯到的字符的下标

    next有这两个作用的源头是:之前提到的字符串的最长相等前后缀
    想一想是不是觉得这个算法好厉害,从而不得不由衷佩服KMP算法的创始人们。

    KMP算法的时间复杂度

    现在我们分析一下KMP算法的时间复杂度:
    KMP算法中多了一个求数组的过程,多消耗了一点点空间。我们设主串s长度为n,子串t的长度为m。求next数组时时间复杂度为O(m),因后面匹配中主串不回溯,比较次数可记为n,所以KMP算法的总时间复杂度为O(m+n),空间复杂度记为O(m)。相比于朴素的模式匹配时间复杂度O(m*n),KMP算法提速是非常大的,这一点点空间消耗换得极高的时间提速是非常有意义的,这种思想也是很重要的。
    下面还有更厉害的,我们一起来分析具体的代码。

    求next数组的代码

    下面我们一起来欣赏计算机如何求得next数组的

    typedef struct
    {	
    	char data[MaxSize];
    	int length;			//串长
    } SqString;
    //SqString 是串的数据结构
    //typedef重命名结构体变量,可以用SqString t定义一个结构体。
    void GetNext(SqString t,int next[])		//由模式串t求出next值
    {
    	int j,k;
    	j=0;k=-1;
    	next[0]=-1;//第一个字符前无字符串,给值-1
    	while (j<t.length-1) 
    	//因为next数组中j最大为t.length-1,而每一步next数组赋值都是在j++之后
    	//所以最后一次经过while循环时j为t.length-2
    	{	
    		if (k==-1 || t.data[j]==t.data[k]) 	//k为-1或比较的字符相等时
    		{	
    			j++;k++;
    			next[j]=k;
    			//对应字符匹配情况下,s与t指向同步后移
    			//通过字符串"aaaaab"求next数组过程想一下这一步的意义
    			//printf("(1) j=%d,k=%d,next[%d]=%d\n",j,k,j,k);
           	}
           	else
    		{
    			k=next[k];
    			**//我们现在知道next[k]的值代表的是下标为k的字符前面的字符串最长相等前后缀的长度
    			//也表示该处字符不匹配时应该回溯到的字符的下标
    			//这个值给k后又进行while循环判断,此时t.data[k]即指最长相等前缀后一个字符**
    			//为什么要回退此处进行比较,我们往下接着看。其实原理和上面介绍的KMP原理差不多
    			//printf("(2) k=%d\n",k);
    		}
    	}
    }
    

    解释next数组构造过程中的回溯问题

    大家来看下面的图:
    下面的长条代表子串,红色部分代表当前匹配上的最长相等前后缀,蓝色部分代表t.data[j]。
    在这里插入图片描述在这里插入图片描述

    KMP算法代码解释

    int KMPIndex(SqString s,SqString t)  //KMP算法
    {
    
    	int next[MaxSize],i=0,j=0;
    	GetNext(t,next);
    	while (i<s.length && j<t.length) 
    	{
    		if (j==-1 || s.data[i]==t.data[j]) 
    		{
    			i++;j++;  			//i,j各增1
    		}
    		else j=next[j]; 		//i不变,j后退,现在知道为什么这样让子串回退了吧
        }
        if (j>=t.length)
    		return(i-t.length);  	//返回匹配模式串的首字符下标
        else  
    		return(-1);        		//返回不匹配标志
    }
    

    KMP算法的改进

    为什么KMP算法这么强大了还需要改进呢?
    大家来看一个例子:
    主串s=“aaaaabaaaaac”
    子串t=“aaaaac”
    这个例子中当‘b’与‘c’不匹配时应该‘b’与’c’前一位的‘a’比,这显然是不匹配的。'c’前的’a’回溯后的字符依然是‘a’。
    我们知道没有必要再将‘b’与‘a’比对了,因为回溯后的字符和原字符是相同的,原字符不匹配,回溯后的字符自然不可能匹配。但是KMP算法中依然会将‘b’与回溯到的‘a’进行比对。这就是我们可以改进的地方了。我们改进后的next数组命名为:nextval数组。KMP算法的改进可以简述为: 如果a位字符与它next值指向的b位字符相等,则该a位的nextval就指向b位的nextval值,如果不等,则该a位的nextval值就是它自己a位的next值。 这应该是最浅显的解释了。如字符串"ababaaab"的next数组以及nextval数组分别为:

    下标01234567
    子串ababaaab
    next-10012311
    nextval-10-10-1310

    我们来分析下代码:

    void GetNextval(SqString t,int nextval[])  
    //由模式串t求出nextval值
    {
    	int j=0,k=-1;
    	nextval[0]=-1;
       	while (j<t.length) 
    	{
           	if (k==-1 || t.data[j]==t.data[k]) 
    		{	
    			j++;k++;
    			if (t.data[j]!=t.data[k]) 
    //这里的t.data[k]是t.data[j]处字符不匹配而会回溯到的字符
    //为什么?因为没有这处if判断的话,此处代码是next[j]=k;
    //next[j]不就是t.data[j]不匹配时应该回溯到的字符位置嘛
    				nextval[j]=k;
               	else  
    				nextval[j]=nextval[k];
    //这一个代码含义是不是呼之欲出了?
    //此时nextval[j]的值就是就是t.data[j]不匹配时应该回溯到的字符的nextval值
    //用较为粗鄙语言表诉:即字符不匹配时回溯两层后对应的字符下标
           	}
           	else  k=nextval[k];    	
    	}
    
    }
    
    int KMPIndex1(SqString s,SqString t)    
    //修正的KMP算法
    //只是next换成了nextval
    {
    	int nextval[MaxSize],i=0,j=0;
    	GetNextval(t,nextval);
    	while (i<s.length && j<t.length) 
    	{
    		if (j==-1 || s.data[i]==t.data[j]) 
    		{	
    			i++;j++;	
    		}
    		else j=nextval[j];
    	}
    	if (j>=t.length)  
    		return(i-t.length);
    	else
    		return(-1);
    }
    

    剩下的话

    在写这篇博客时,我想起了编译原理老师讲过的一些知识,其实KMP算法的步骤与自动机有不少相似之处,有兴趣的朋友不妨联系对比一下。

    参考书籍

    《数据结构教程》(第5版) 李春葆
    《大话数据结构》 程杰

    展开全文
  • 严蔚敏数据结构kmp算法详解PPT学习教案.pptx
  • KMP

    一. 模式匹配

      当有两个字符串Str = "abdabcde;modStr = "abcd";时,如果要在Str中查找与modelStr相等的子串,则称Str为主串,modelStr为模式串。在查找过程中,从Str中的第一个字符进行比较,如果找到与modelStr相同的子串,函数返回modelStr字符串第一次出现的位置,否则返回-1。以上过程就称为模式匹配.

    二. 模式匹配算法

      模式匹配算法,最广为人知的有两种算法,一种为简单且暴力的BF算法,一种为效率极高的KMP算法。下文将会对两种方法进行详解。

    1. 朴素模式匹配算法

      BF算法为朴素模式匹配算法的经典,该算法的主要思想,从主串的第一个字符与模式串中的第一个字符进行比较,若相等则继续比较,若不相等则从主串中不相等的位置与模式串中的第一个字符进行比较。
    在这里插入图片描述
      指针i指向主串,j指向模式串,当匹配失败时,i移动的位置为i = i - j + 1
      当所有字符串匹配成功后,指针j指向了模式串末尾的下一个,在进行匹配的过程中,不难发现,当每次匹配失败后,i指针都进行了不必要的回溯,这个回溯过程造成了时间的大量浪费。

    2. KMP算法

    1). KMP算法的优势

      上文讲述了BF算法的实现,也阐述了BF算法的效率低下之处,KMP算法就是针对BF算法的改良,当进行模式匹配时,出现字符比较不等的情况,不用回溯i指针,而是利用已经匹配过后的结果,向右尽可能滑动的稍远一些,再继续进行比较。

    2). KMP算法的原理

      以字符串Str = "acabaabaabcacaabc";modStr = "abaabcac";为例,进行说明:
      当i=8, j=6时,发现匹配失败: 如果按照BF算法, i指针会回溯至4的位置重新开始比较。但是这种i的回溯是有必要的吗?显然duck不必。
      观察一下,j1=j4, j2=j5且i3=j1,i4=j2,所以回溯i指针到4的位置完全没有必要,根据上述等式关系,我们只需要将j指针的位置移动到j4的位置重新开始匹配。
    在这里插入图片描述
      再看一个例子: str=“aabababcaad” modStr=“babc”,当i=6, j=4时发生失配,但j1=j3,所以直接将j指针移动到j4的位置,开始匹配。
    在这里插入图片描述
      再看最后一个例子,str=“aacabcd”, modStr=“abcd,当发生失配时,怎么操作。
      在发生失配时,将i指针向后移动一位,继续进行比较。
    在这里插入图片描述
      综合上述例子,不难看出模式串中存在着字符相同的元素,在模式串的子串中构成了前缀与后缀。并且在失配之后对于`i指针的移动存在一定的规律,从而引出了next数组的概念,next数组用于存放模式匹配失配时,模式串的滑动距离。

    3). next数组的构造

      通过上述的例子,已经得知next[]数组存放的内容为,模式串与目标串匹配失败时用于寻找模式串回溯位置的数组。
      如何计算next数组呢?其中最重要的概念就是最大前缀与最大后缀。
    在这里插入图片描述
      公式是这样表示最大前缀与最大后缀的,但是实际中如何求解呢。str="abaabcac"以这个字符串为例,表示出它的前缀与后缀。
    在这里插入图片描述
      对于这个字符串它的前缀与后缀是这样的,所以它的最大前缀=最大后缀的字符串是a;
      接下来就要通过这个最大前缀=最大后缀的概念,来进行失配后模式串回溯的位置计算。

      设模式串为abaabcac( j指向的位置为当前匹配位置,假设在当前位置失配,求出在当前位置失配的回溯位置,j指针前方字符串为要计算回溯位置的子串)
    1.j=1失配 (因为j=0 所以next[j]=0)
    在这里插入图片描述
    2.j=2失配 (没有前后缀,属于其他情况)
    在这里插入图片描述
    3.j=3失配(前缀不等与后缀)
    在这里插入图片描述

    4.j=4失配(最大前缀=最大后缀,所以k=2)
    在这里插入图片描述
    5.j=5失配
    在这里插入图片描述
    6.j=6失配 (最大前缀 ab = 最大后缀 ab, 所以k=3)
    在这里插入图片描述
    7.j=7失配
    在这里插入图片描述
    8.j=8失配

    在这里插入图片描述

      以上为next数组求法,但字符串下表一般从0开始,所以要对next数组中元素-1,得在这里插入图片描述
    至此,next数组已经求解完毕,如何利用next数组进行模式匹配,继续阅读下文。

    4). 利用next数组匹配的过程

      在这一部分,将会说明模式匹配是如何利用next数组进行模式匹配。
      以str = "acabaabaabcacaabc";modStr = "abaabcac";为例,字符串下标从0开始,进行说明:在这里插入图片描述

    1.第一次匹配(i=1,j=1位置发生失配)
    根据next数组可知,将j指针回溯到j0位置进行重新匹配。 在这里插入图片描述

    2.第二次匹配(i=1,j=0位置发生失配)
    next数组中没有相关跳转位置,所以i指针后移一位,开始匹配。 在这里插入图片描述

    3.第三次匹配(i=7,j=5位置发生失配)
    根据next数组,可知j回溯到 2的位置重新开始匹配 在这里插入图片描述
    4.匹配成功在这里插入图片描述
    以上就为KMP算法的匹配过程。

    二. KMP算法的代码实现

    1. 生成next[]数组

    void getNextArr(string modelStr, int* next)
    {
    	// 初始化next数组第一位为-1
    	int i = 0;
    	int j = -1;
    	next[0] = -1;
    
    	int mLen = modelStr.length();
    
    	while (i < mLen - 1)
    	{
    		// 求最大前缀=最大后缀的过程
    		if (j == -1 || modelStr[i] == modelStr[j])
    		{
    			i++;
    			j++;
    			next[i] = j;
    		}
    		else
    		{
    			// 当没有匹配上 则进行回溯 回溯的位置为next数组的指向的下一个匹配项
    			j = next[j];
    		}
    	}
    }
    

    2. KMP查找过程代码

    // 如果查找成功返回位置
    // 如果查找失败返回-1
    int KMP(string dstStr, string modelStr)
    {
    	int i = 0;
    	int j = 0;
    
    	int dstlen = dstStr.length();
    	int modellen = modelStr.length();
    
    	int next[255] = { 0 };
    
    	getNextArr(modelStr, next);
    
    	while ((i < dstlen) && (j < modellen))
    	{
    		if (j == -1 || dstStr[i] == modelStr[j])
    		{
    			i++;
    			j++;
    		}
    		else
    		{
    			j = next[j];
    		}
    	}
    
    	if (j >= modellen)
    	{
    		return i - modellen;   // 匹配成功 返回子串位置
    	}
    	else
    	{
    		return -1;
    	}
    }
    
    展开全文
  • 有这样一个问题: 给定一个字符串(模式串S):"BBC ABCDAB ABCDABCDABDE" 我想知道其中是否包含(模板串P)"ABCDABD" ? ...1.2 KMP思路 Knuth、Morris、Pratt三个学者提出这样一种方法:就这个例

    有这样一个问题:
    给定一个字符串(模式串S):"BBC ABCDAB ABCDABCDABDE"
    我想知道其中是否包含(模板串P)"ABCDABD" ?

    1 两种字符串匹配思路

    1.1 暴力思路 O(m * n)

    想象两把尺子,S是上面的长尺,P是下面的短尺,最开始两个尺子左端对齐,下面的短尺从左到右一位一位移动,直到匹配成功。
    比如:当下面的尺子对齐了上面的 ABCDAB,但是 D 对应的是空格,这时匹配失败,只能往右再一位一位移动
    暴力实现的代码可以参考如下:

    char p[N], s[M];
    for(int i = 1; i <= m; i ++){
    	bool flag = true;
    	for(int j = 1; j <= n; j ++){
    		if(s[i + j - 1] != p[j]){
    			flag = false;
    			break;
    		}
    	}
    }
    

    1.2 KMP思路 O(m + n)

    Knuth、Morris、Pratt三个学者提出这样一种方法:就这个例子而言,当 D 对应的是空格时,我们并没有前功尽弃,因为我们已知 D 前面的 ABCDAB 是已经正确匹配的,同时我们发现正确匹配的字符串前后两端都有 ABABCDAB),那么我们可以直接向后移动 4 位,继续去匹配空格,观察能否匹配成功,即:

    • 初始
      BBC ABCDAB ABCDABCDABDE
      XXX ABCDABD
    • 向后移动4位
      BBC ABCDAB ABCDABCDABDE
      XXX XXXXABCDABD
    • 注:X代表检查过的

    如果空格匹配成功则继续,匹配失败的话可以再观察是否有类似“回文”1的形式,如果有的话可以一次移动多位,如果没有只能一位一位移了。(实际上还剩下的AB已经不具备跳着移动的条件了,如果仍然无法匹配,只能全部移过去从头开始了)
    1:“类似”的含义是:ABAB不是回文形式,ABABA是回文形式,两者都可以跳着走。

    我们再给一个例子来感受KMP:
    模式串S:ababaeaba
    模板串P:ababacd

    • ababaeaba
      ababacd
      'c’无法与’e’匹配,观察到"ababa"的头是"aba",尾也是"aba",那么可以直接移2位
    • ababaeaba
      xxababacd
      'b’仍然无法与’e’匹配,观察到"aba"的头是"a",尾也是"a",那么可以直接移2位
    • ababaeaba
      xxxxababacd
      'b’无法与’e’匹配(紧跟亮色后面的),只剩a也不能跳着走了,这样就只能从e开始重新来了。

    如果是暴力的话,第一次匹配不到e,可能就是这样的结果:(一位一位移动看是否能匹配)

    • ababaeaba
    • xababacd
    • xxababacd

    2 概念补充

    2.1 模式串和模板串

    s[ ]是模式串,即比较长的字符串。
    p[ ]是模板串,即比较短的字符串。(这样可能不严谨

    2.2 前缀后缀

    “非平凡前缀”:指除了最后一个字符以外,一个字符串的全部头部组合。
    “非平凡后缀”:指除了第一个字符以外,一个字符串的全部尾部组合。
    以下均简称为前/后缀。

    举例:P = abcab,假设下标从1开始,分别对应1、2、3、4、5

    下标前缀后缀
    1
    2{ a }{ b }
    3{ a, ab }{ c, bc }
    4{ a, ab, abc }{ a, ca, bca }
    5{ a, ab, abc, abca }{ b, ab, cab, bcab }

    2.3 next数组

    在上面的例子中,我们每一次应该向右直接移动多少位是通过next数组得到的,而next数组是经过预处理得到的。
    简单的来讲,next数组可以这样通俗地描述:
    next[i]:以i为终点的后缀和从1开始的前缀相等,且长度最长。数组中存放的是这个前缀的最后一个元素的下标。(因为这样才能拼接过去)

    // 伪代码形式
    next[i] = j;
    p[1, j] = p[i - j + 1, i]
    

    还是刚刚那个:P = abcab

    下标 i前缀后缀next[i]
    10
    2{ a }{ b }0
    3{ a, ab }{ c, bc }0
    4{ a, ab, abc }{ a, ca, bca }1
    5{ a, ab, abc, abca }{ b, ab, cab, bcab }2

    eg.对5来说,next[5] = 2的含义就是:p[1 ~ 2] = p[4 ~ 5]

    3 代码实现

    3.1 next数组的应用

    有了next数组,我们每次匹配不成功时,就可以直接得出下一个跳向哪个位置,这一操作可以直接由j = next[j]来完成。
    插句题外话,在y总眼里,这是 j 的回退,其实 j 每次回退,都是P串在跳跃行进匹配的过程。
    假设我们已经有了next数组,那么kmp匹配的过程可以用代码表示如下:

    int ne[N];	// next数组
    // kmp 匹配过程
    for(int i = 1, j = 0; i <= m; i ++){
    	while(j && s[i] != p[j+1]) j = ne[j];	// 当j没有回退起点 且 当前的S[i]无法匹配时
    	if(s[i] == p[j + 1]) j ++;
    	if(j == n){
    		/*
    		匹配成功
    		*/
    		j = ne[j];	// 继续寻找下一个匹配串
    	}
    }
    

    贴一张y总上课讲的抽象图:(配合上面代码)
    在这里插入图片描述

    3.2 next数组的初始化

    先给一个例子,便于下面算法的模拟,顺便看看对next数组是否理解了:
    P = ababa,则:(始终记住KMP算法中下标我们都从1开始

    next[ i ]初始化依据
    10
    20
    31a
    42ab
    53aba

    next数组的初始化的本质就是自己和自己匹配
    一定要想清楚在kmp匹配过程中,P字符串的 j 到底意味着什么:j 的作用就是下一次 P 字符串的开始匹配点(的前一个)。
    通俗的讲,j 就是在P串中能匹配到哪,记录每一个能匹配到哪的位置就是next的初始化过程。
    好难描述我脑海中的动图,希望以后的我能看懂……

    • 最开始
      j = 0 ababa
      i = 2 baba 无法匹配到,所以ne[2] = 0
    • i = 3 aba 匹配到了,j = 1,所以ne[3] = 1
    • i = 4 ba 匹配到了,j = 2,所以ne[4] = 2
    • i = 5 a 匹配到了, j = 3,所以ne[5] = 3
    • 如果匹配不到的话,也不用一步一步挪,直接用已经有的ne[j],匹配的会更快

    代码写出来和3.1几乎一样,毕竟都是匹配的过程。

    for(int i = 2, j = 0; i <= n; i ++){
    	while(j && p[i] != p[j + 1]) j = ne[j];
    	if(p[i] == p[j + 1]) j ++;
    	ne[i] = j;
    }
    

    3.3 总代码

    总结:KMP算法可以实现字符串的快速匹配问题
    题目链接:KMP匹配字符串

    #include<iostream>
    
    using namespace std;
    
    const int N = 100010;
    const int M = 1000010;
    char p[N], s[M];
    int ne[N];
    int main(){
        int m, n;
        cin >> n >> p + 1 >> m >> s + 1;    // 保证下标从1开始(优雅来自于细节啊)
        
        // 求next
        for(int i = 2, j = 0; i <= n; i ++){
        	while(j && p[i] != p[j + 1]) j = ne[j];
        	if(p[i] == p[j + 1]) j ++;
        	ne[i] = j;
        }
        
        // kmp匹配
        for(int i = 1, j = 0; i <= m; i ++){
        	while(j && s[i] != p[j+1]) j = ne[j];	// 当j没有回退起点 且 当前的S[i]无法匹配时
        	if(s[i] == p[j + 1]) j ++;
        	if(j == n){
        		printf("%d ", i - n);
        		j = ne[j];	// 继续寻找下一个匹配串
        	}
        }
        return 0;
    }
    

    4 参考

    [1] 字符串匹配的KMP算法–前缀和后缀的详解
    [2] AcWing 831. KMP字符串-题解

    展开全文
  • 二、KMP算法的解决题型三、模式串移动距离的判断(next数组)四、KMP算法的具体实现五、KMP算法的时间复杂度六、next数组的改进--nextval数组及具体代码七、最后的话 一、什么是KMP算法KMP算法是一种改进的字符...
  • KMP算法详解

    千次阅读 多人点赞 2019-03-15 19:44:33
    KMP算法是求解主串(以下简称为s)和模式串(以下简称为p)匹配问题的O(n)算法。 其核心思想就是,当s[i]和p[j]发生不匹配现象时,i指针不需要回溯,只需j指针回溯。 例如: 当s[i]和p[j]发生失配,一种暴力的方法...
  • KMP算法解析 KMP算法是一种匹配算法,用来进行匹配查找。 通过在子串的每一位都设置一个与之对应的回溯数组下标,降低算法的时间复杂度。 每一个需要查找的子串,该算法都会给它生成一个与之相对于的next数组,用来...
  • 数据结构KMP算法

    千次阅读 2018-10-18 17:39:06
    KMP算法是用来处理字符串匹配的。换句话说,给你两个字符串,你需要回答,B串是否是A串的子串(A串是否包含B串)。例如”Today is Tuesday”.中是否包含”day”,在哪些位置包含。 这个算法是由Knuth、Morris、...
  • 数据结构-KMP算法详解

    2021-10-17 11:35:45
    KMP算法的核心就在于如何在模式串的前缀中找到合适的字符作为下一次匹配过程的新起点,而不是简单的从模式串的起始位置重新开始匹配,从而减少匹配次数,提高效率。 构造查询表next[0,m) 为确定模式串下一次匹配过程...
  • 看了一晚上终于明白这个KMP算法是什么意思,果然只要是想学习,就能学会呀,谢谢这两篇博客 见网址http://www.cnblogs.com/SYCstudio/p/7194315.html和https://blog.csdn.net/f1033774377/article/details/82556438...
  • 在复习数据结构课程的过程中 对kmp算法及next数组的求解过程进行了深度探索 内含具体代码 及求解next数组的详解 望对大家有所帮助
  • 主要介绍了JavaScript中数据结构与算法(五):经典KMP算法,本文详解KMP算法的方方面在,需要的朋友可以参考下
  • KMP算法代码详解

    千次阅读 2020-09-03 02:00:57
    学习了kmp算法,思想其实很好理解,但是代码的实现一直看得很迷糊。看了很多博客,特别是对匹配信息的next数组有很多不同,比如数组有首位有-1的也有0的等。我自己也疏离了一遍,记录一下,方便之后以后回忆。 首先...
  • 本文主要对KMP算法进行介绍 KMP算法是一个序列匹配的算法,比如有两个序列s1和s2,想知道s1中是不是有一个和s2相同的子串,如果有,返回匹配的起始位置。 最直觉最暴力的方法就是依次从s1的任何一个位置去匹配s2,...
  • 大名鼎鼎的KMP算法 来吧今天我们一起搞懂它!???? 首先不太清楚KMP算法的可以戳这里!百度百科欢迎您~ KMP算法简介: KMP算法是一种改进的字符串匹配算法。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主...
  • kmp
  • 通俗易懂的KMP算法详解(严蔚敏版C语言)

    万次阅读 多人点赞 2019-03-16 00:12:26
    最近,需要复习KMP算法的next数组,然后回头看半年多后的我回头看半年多前自己综合别人内容写的介绍。 没错,自己也看不懂。然后,自己再根据自己的理解写了一下理解透彻的笔记,方便理解记忆,当然,以前的代码解释...
  • KMP算法 1、背景 KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的,称之为 Knuth-Morria-Pratt 算法,简称 KMP 算法。该算法相对于 Brute-Force(暴力)算法有比较大的改进,主要是消除了主串...
  • 数据结构KMP 模式匹配详解 通俗易懂

    千次阅读 多人点赞 2021-01-02 13:05:40
    KMP 模式匹配详解通俗易懂 KMP 模式匹配是解决字符串匹配的问题 一、原始的字符串暴力匹配 要点:子串的第一个字符匹配成功主串的字符后就依次匹配子串后面的字符,直到子串匹配结束 代码: public static int ...
  • 文章目录简介一般的解法-BF算法BF算法思想图解程序代码KMP算法算法引入难点突破移动问题思路分析next数组详讲完整算法展示next数组求解算法优化 简介      KMP 算法是 D.E.Knuth、J,H,Morris 和...
  • KMP算法详解0.0.doc

    2019-05-09 10:25:38
    KMP算法详解0.0.doc,希望对在学数据结构与算法或对之感兴趣的人有所帮助!
  • 这周在学数据结构常见算法时遇到了很多的坑,真的是一步一个坑,先是背包问题,又是这个KMP算法,听的是尚硅谷韩老师的java数据结构与算法,他刚开始讲的算法思路还是听清晰的,但是一到代码上… 一言难尽。KMP最...
  • KMP 算法(Knuth-Morris-Pratt 算法)是一个著名的字符串匹配算法,效率很高,但是确实有点复杂。 很多读者抱怨 KMP 算法无法理解,这很正常,想到大学教材上关于 KMP 算法的讲解,也不知道有多少未来的 Knuth、...
  • KMP算法详解及C++实现

    2021-10-04 14:29:24
    目录一、介绍KMP算法解决的问题二、KMP算法的核心思想三、KMP的代码实现(C++) 一、介绍KMP算法解决的问题 KMP算法实际上解决的是一个字符串匹配的问题,即从一个目标字符串(通常非常长)中找到与给定字符串(也...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,366
精华内容 946
关键字:

数据结构kmp算法详解

数据结构 订阅