美文网首页
KMP简单理解

KMP简单理解

作者: A黄橙橙 | 来源:发表于2020-03-03 01:51 被阅读0次

理解KMP,我们先简单看一下这个过程。

对于abx--aby--这个匹配串,如果我们能够顺利匹配完y之前的字母,一个一个往后移动是意义不大的,最好的情况就是直接把第一个abx后移到aby匹配的位置,看一下x能否匹配上,如果匹配上了,就继续向后尝试匹配;如果没匹配上,说明这个abx也没用,可以直接将a移动到x后面一个字母上尝试匹配。

两个相同子串ab移动的过程,就需要要预处理,即next数组,在说next数组之前,我们先来引入两个概念,理解这两个概念,是理解KMP的关键!

前缀就是以某一个字母开头的所有字母集合;后缀就是以某一个字母结尾的所有字母集合。

仍然以abx--aby--的匹配串作为例子,对于aby--中的b来说,b有一个后缀ab,对于abx--来说,a有一个前缀ab,此时这两个前后缀子串刚好相等。也就是说,当我们在匹配过程中,假设文本串为--abx--abz--,指针在比较 y!=z ,next数组让指向y的指针改指向x,若x!=z,那么直接重新匹配(此时后移了很多);若x==z,那么指针后移继续尝试匹配。

再次强调一下,在KMP中运用的前缀一定是以匹配串第一个字母开头的前缀(这样才能移动!),后缀一定是指以当前这个字母之前的一个字母作为结尾的后缀(这样在匹配到不相同的时候才好确认之前的字母是相同的)。

如果
原始的next数组:

void Next(char* p,int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀,p[j]表示后缀  
        if (k == -1 || p[k] == p[j])   
        {  
            ++k;  
            ++j;  
            next[j] = k;  
        }  
        else   
        {  
            k = next[k];  
        }  
    }  
}  

研究一下代码是怎么操作的,看起来很简单,理解起来还是有几分复杂。

最重要的在注释中写了。既然j和k代表不同含义,我们看一下它的初值情况,本身就是不同步的,(k==-1会直接进入)相当于k是指向第一个元素,j是指向第二个元素。

继续研究j和k,我们发现,j只有第一个if是有变化的,而且只有++,所以是硬加的,相当于遍历整个匹配串,给匹配串上面标注0.1.2.3...的下标。

我们注意到k++的情况,只有在p[k]==p[j]的时候,极端情况,他们一直相等,此时k是从0(其实应该说-1)开始的,一直加的过程中,都保证了与p[j]的相同,就相当于k有多长(前缀),j也同时加了多长(后缀),所以对每一个j的next都标注一下此时与k这么长的前缀是相等的。

再说一个if里面的点,就是j始终要比k大,同时还要next[j]=k,所以表达的含义是【以字母前一个字母作为后缀能达到的最长】

至于else里面的内容,暂时我只能肤浅得认为,以abx--aby--做例子,当j指向b的时候,先进if,使得y对应的next已经记录了2,然后再次循环,j不变,进入else语句,next[2]明显是等于0的,所以相当于把k的数字调整到上一次达到的状态,这个next数组涉及了有限自动机,等后面好好看一下再聊吧。

认真看看这个再来谈吧从头到尾彻底理解KMP-Chris_z)

相关文章

  • KMP简单理解

    理解KMP,我们先简单看一下这个过程。 对于abx--aby--这个匹配串,如果我们能够顺利匹配完y之前的字母,一...

  • 理解KMP算法

    简单理解KMP 本文读者可以获得两方面的知识 直观理解如何生成部分匹配表(下文简称匹配表),这是KMP算法的核心思...

  • 对KMP算法的一些理解

    最近学到KMP算法,下面讲讲对KMP算法的一些个人理解,希望对大家有帮助! 对于KMP算法的理解: 整个KMP算法...

  • KMP实现

    kmp next数组 理解

  • KMP算法学习札记

    参考文章 知乎:如何更好的理解和掌握 KMP 算法?从头到尾彻底理解KMPKMP 算法(1):如何理解 KMP(原...

  • kmp 算法

    前言: 少 kmp 多学习 0X00 算法板子 831. KMP字符串 感觉还是很难理解

  • 字符串匹配: KMP算法

    字符串匹配: KMP算法 学习于 从头到尾彻底理解KMP 结合自己的理解, 本文致力于从简介绍 先给出模板代码v...

  • 数据结构与算法14-字符串匹配与KMP

    什么是KMP KMP算法是在字符串匹配算法中比较绕的.主要是需要理解KMP中next数组求解的必要性以及j 的回溯...

  • 字符串匹配问题-KMP算法

    什么是KMP KMP算法是在字符串匹配算法中比较绕的.主要是需要理解KMP中next数组求解的必要性以及j 的回溯...

  • 理解 KMP 算法

    1. 概述 字符串是编程中常用的一种数据结构,在各个方面都有广泛的应用,而字符串的一种基本操作就是给定一段长度为N...

网友评论

      本文标题:KMP简单理解

      本文链接:https://www.haomeiwen.com/subject/pkankhtx.html