00问答网
所有问题
模式匹配KMP算法里面next里保存的值有什么用?
如题所述
举报该问题
推荐答案 2011-04-22
next数组存储的数据是用来当模式串与主串不匹配的时候要模式串回退到第几个字符与主串再重新匹配,我们知道KMP算法的主串是不回朔的,当不匹配的时候我们不是退回到开始位置重新匹配,而是利用已经匹配的结果将模式串回朔到下一个位置,这个位置比开始位置更近一步;
简单的说就是next[ j ]的值保存的是当模式串中第 j 个字符与主串第 i 个字符不匹配时候,模式串中的哪个字符 重新与主串第 i 个再匹配,这样总的字符比较次数比从开始位置比较的次数就少了。
温馨提示:答案为网友推荐,仅供参考
当前网址:
http://00.wendadaohang.com/zd/njjj0Bjer.html
相似回答
KMP算法
(
next
数组、nextval数组、有限自动机【AC自动机】)———附带...
答:
KMP算法
:智能
匹配的
艺术,通过巧妙利用
next
数组和nextval数组,实现高效字符串匹配的高效算法——有限自动机【AC自动机】。它以精准的步调,避免了不必要的字符比较,节省了宝贵的时间。核心思想在于next数组,它定义了
模式
串中失配时,子串需要重新开始比较的位置。每个next[i]代表模式串中第i个字符与主...
kmp算法中的next
到底是
什么
意思啊?
答:
1.第一位的
next值
为0 2.第二位的next值为1 后面求解每一位的next值时,根据前一位进行比较 3.第三位的next值:第二位的
模式
串为b ,对应的next值为1;将第二位的模式串b与第一位的模式串a进行比较,不相等;则第三位的next值为1 4.第四位的next值:第三位的模式串为a ,对应的next值...
关于KMP算法
问题
答:
next值
:001012 假设k当前等于2时,那么如果此时
模式
串与主串发生失配时,就有k=nextval[2]=1,即模式串与主串匹配到第2个字符时发生失配,那么后缀指针无需回溯,前缀指针只需回溯到第1个字符的位置并且继续与主串的第2个字符匹配。这样就可以加快
匹配的
速度,因为后缀指针不用再回溯。即教材所说...
kmp算法
详细算法
答:
例如在'abcdaabcab'这个例子中,通过调整next数组来提高
匹配
效率。在
KMP算法的
实现中,例如在C++中,我们有get_nexst和COUNT_KMP函数,它们分别用于计算
模式
串的
next值
以及在主串中查找模式串的个数。Pascal版本的KMP算法也有index函数,用于查找模式串在原串中的位置。
大家正在搜
算法KMP模式串匹配的伪代码
算法KMP模式串匹配
字符串的kmp模式匹配算法
模式匹配算法
kmp算法进行模式匹配
C语言改良模式匹配算法
kmp算法特点是在模式匹配
kmp算法nextval匹配过程
函数kmp实现串的模式匹配
相关问题
在KMP模式匹配中,用next数组存放模式串的部分匹配信息?
串模式匹配的kmp算法中next[0]的值到底是0还是-1;...
kmp算法中的next到底是什么意思啊?
看KMP算法中的next函数很多次了 始终不明白!求高手详细...
那个,KMP算法里面 求模式串的next[]数组的方法看不懂...
已知一个模式串T="aaaba",则在KMP算法中,其nex...
模式串t="abaaabb"在kmp模式匹配算法中,该模式串...