KMP算法中的next数组的求法
从《严书》上看到了KMP算法,看了一遍没懂,但觉得挺神奇的,就花费了几天时间深入的理解。
算法的原理其实不难,难的就是那个巧妙的next数组,这个next数组很吸引我,我的大部分时间也都是花费在这个数组上面的。这个next数组是KMP里面一个很关键的地方,对于在数据结构书上看过一遍整个算法流程的人,能够把next数组搞明白,整个KMP算法的整体思想就差不多理解了。然后在一些细节上面深入思考一下,就可以理解和领会改进的KMP算法。
一、KMP算法简单介绍
KMP算法是字符串匹配算法的一种,相对于朴素的字符串匹配算法而言,可以大大避免重复遍历的情况。此算法可以在O(n+m)的时间数量级上完成字符串匹配操作。
二、神奇的next数组
关于KMP算法的原理和实现,书上或者百度一下都可以找到,我在这里就不罗嗦那么多了,直接切入主题(next数组)。
我们设主串S=abcabcabca,模式串p=abcabx。
KMP第一趟匹配:
i=6
S : a b c a b c a b c a
位置 : 1 2 3 4 5 6 7 8 9 10
P : a b c a b x
位置 : 1 2 3 4 5 6
j=6
第一次匹配到第6个位置的时候失败了,按照朴素的算法,i要回溯到第2个位置,j要回溯到第1个位置重新匹配。KMP的话,主串中的i是不会回溯,模式串中的j回溯也不会回溯到第1个位置。注意这里是关键,i不用回溯就可以完成整个字符串的匹配。为什么i不需要回溯呢?我们先留下这个疑问。
我们把匹配成功的前5个字符研究一下。
1位置的前缀子串为:a , ab , abc , abca
5位置的后缀子串为:bcab , cab , ab , b
我们观察发现两组里面都有一个ab,你能看出点什么东西么,好的,先不管这个。
我们就按照朴素的算法来看,i回溯到第2第3位置都会在前5个字符中匹配失败。
朴素匹配:
i=4
S : a b c a b c a b c a
位置 : 1 2 3 4 5 6 7 8 9 10
P : a b c a b x
位置 : 1 2 3 4 5 6
j=1
当回溯到第4个位置的时候,成功匹配的字符为ab,然后再去判断S串的第6个字符和P串的第3个位置。这个然后我们先不管,观察S中和P匹配的ab,在第一趟匹配的时候S中的ab是和P中前5个字符的最后两个匹配的,而这一次匹配则是和P中前两个字符匹配的。能发现点什么东西么?
不需要让i回溯到之前的位置重新匹配,只需要找到在P串前5个字符中第一个位置的前缀子串和最后一个位置的后缀子串相等并且串长最大的那一对子串,让j指向前缀子串最后一个字符的下一个位置3,和i所指向的6进行比较。往后遇见不匹配的时候采取和这个一样的方法。
KMP第二趟匹配:
i=6
S : a b c a b c a b c a
位置 : 1 2 3 4 5 6 7 8 9 10
P : a b c a b x
位置 : 1 2 3 4 5 6
j=3
这个时候就需要next数组的建立了,
next[6]存储的就是前5个字符组成的字符串中的第一个位置的前缀子串和最后一个位置的后缀子串相等并且串长最大的那一对子串的最后一个字符的下一个位置,也就是3,也就是和P串中第3个位置匹配。
写到这里,next数组应该可以得出来了。
具体代码怎么得出来的,书上面都有。。那个应该不难。
分享到:
相关推荐
KMP算法中next数组求法.docx
关于KMP算法中next数组的计算方法研究
在复习数据结构课程的过程中 对kmp算法及next数组的求解过程进行了深度探索 内含具体代码 及求解next数组的详解 望对大家有所帮助
关于字符串匹配里,KMP算法中next实现实现原理。关于字符串匹配里,KMP算法中next实现实现原理。
这是基于严蔚敏数据结构中有关KMP算法的NEXT数组的计算过程,与书中的例子基本一致,是学习数据结构字符串KMP算法的一个很要的理解内容。
KMP算法中求NEXT的方法,希望对大家有所帮助啊,呵呵!!!
kmp算法中得next数组也叫fail数组的计算很难理解且代码也不容易实现,本代码就是计算fail数组的源代码
KMP算法求next数组这篇博客中有几张图片,但是博客中图片是竖着的,不方便查看,但我又不知道如何旋转图片,提供博客中的图片,方便下载到自己的电脑上进行查看
也就是说,KMP算法是用来解决字符串匹配问题的,从一个主字符串text中寻找一个子字符串(模式字符串)pattern,看这个子串是否在主串中,比如对于text='abaacababcac'和pattern='ababc',子串是包含在主串中的,同时它...
也就是说,KMP算法是用来解决字符串匹配问题的,从一个主字符串text中寻找一个子字符串(模式字符串)pattern,看这个子串是否在主串中,比如对于text='abaacababcac'和pattern='ababc',子串是包含在主串中的,同时它...
*KMP算法的思想就是在匹配过程称若发生不匹配的情况 *如果next[j]>=0则目标串的指针i不变将模式串的指针j移动到next[j]的位置继续进行匹配 *若next[j]=-1则将i右移1位并将j置0继续进行比较 *...
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
第一部分、KMP算法初解 1、普通字符串匹配BF算法与KMP算法的时间复杂度比较 2、BF算法与KMP算法的区别 3、BF算法为什么要回溯 4、KMP 算法思想 ...第二部分、next数组求法的来龙去脉与KMP算法的源码
使用KMP算法实现模式匹配,包括next数组的求解,kmp算法的实现。关键代码有详细注释。
在匹配过程中,当发现当前字符不匹配时,KMP算法会根据next数组的值来确定下一次匹配开始的位置,从而避免了不必要的比较操作。 KMP算法的时间复杂度为O(m+n),其中m和n分别为主串和模式串的长度。这种高效的性
具体来说,KMP算法通过预处理模式串P,构建一个部分匹配表(也称为next数组),然后利用这个部分匹配表在匹配过程中跳过一些不可能匹配的位置,从而提高匹配效率。 KMP算法的时间复杂度为O(m + n),其中m为文本串S...
KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的回溯次数,从而提高匹配效率。 适应人群: KMP算法适合以下人群: 1. 程序员:在开发过程中,程序员需要进行大量的字符串匹配...
KMP算法通过使用一个称为“部分匹配表”或“next数组”的数组来减少字符串匹配过程中的回溯次数,从而提高匹配效率。 适应人群: KMP算法适合以下人群: 1. 程序员:在开发过程中,程序员需要进行大量的字符串匹配...
KMP算法的核心在于构建一个名为“Next数组”的辅助数组,该数组用于存储模式串中每个位置前的子串的最长相同前后缀的长度。当主串中的字符与模式串的字符不匹配时,可以根据Next数组的值,快速将模式串滑动到正确的...