KMP算法的C++实现,解决下标0和总是输出负数

   日期:2020-10-16     浏览:105    评论:0    
核心提示:KMP算法的C++实现,解决下标0和总是输出负数个人第一次学习数据结构,请各路大神键下留情《大话数据结构中》KMP模式匹配算法,下标从1开始,个人三天前才开始学习数据结构,看到此章节,停留了两天,对自身遇到的问题进行错题记录。解决下标0的问题大话数据结构中,求取模式串next数组的源码如下可以明显得知,该方法是以下标“1”为起始,如果在C++中,直接复制此段代码,会出现如下情况:总结问题即为:无法识别模式串的下标0是否与主串匹配,单纯通过判断下标1之后的模式串来进行匹配,显而易见时错误的。

KMP算法的C++实现,解决下标0和总是输出负数(需要完整代码可在评论区评论,会及时回复)

个人第一次学习数据结构,请各路大神键下留情,另外由于等级不够,无法上传代码,需要完整代码,可在评论区评论,会及时回复。

《大话数据结构》中KMP模式匹配算法,下标从1开始,个人三天前才开始学习数据结构,看到此章节,停留了两天,对自身遇到的问题进行错题记录。

解决下标0的问题

大话数据结构中,求取模式串next数组的源码如下

可以明显得知,该方法是以下标“1”为起始,如果在C++中,直接复制此段代码,会出现如下情况:

总结问题即为:无法识别模式串的下标0是否与主串匹配,单纯通过判断下标1之后的模式串来进行匹配,显而易见时错误的。

next数组的解决办法


由于if条件中,存在t[ i ] == t[ j ],因此,将各个数字-1即可。
我的思路是这样:
1.下标从1开始时,第一个比较式为t[ 2 ] 与 t[ 1 ],目的让第一个比较式变为t[ 1 ] 与 t[ 0 ]。
2.下标从1开始时,原式会由于j=0,而比较t[ 2 ] 与 t[ 1 ]。那么,若条件为j= -1,则会比较
t[ 1 ] 与 t[ 0 ]。
多拿笔写写,画画,思路就出来了。

next数组下标从0开始,在最终匹配时总是输出错误

这个错误的原因,是由于while循环条件导致的,接着看,

即便next数组改为从0开始,依然会输出错误,此时要注意第36行,循环条件是:int型与size_t型的比较,而当出现int值为-1时,会直接跳出循环,导致错误。
如果不信,可以设置如下主串和模式串,并加一行判断代码,判断串和判断代码如下图



由前面的KMP算法可知,当s[0] != t[0],且ix != -1,会进入ix = next[ix] = next[0] = -1;
接着++id,++ix,然而此时的调试结果并没有输出第42行的内容,而是直接跳出while循环。
也就是说,当ix = -1时,由于不满足循环判断条件而直接输出,导致结果出错。

while判断条件解决办法


(注意:上图的i = id,j = ix,实质上没有区别)将s.size(),t.size()都定义为int类型变量,即可成功输出

补全绿色注释。

 
打赏
 本文转载自:网络 
所有权利归属于原作者,如文章来源标示错误或侵犯了您的权利请联系微信13520258486
更多>最近资讯中心
更多>最新资讯中心
0相关评论

推荐图文
推荐资讯中心
点击排行
最新信息
新手指南
采购商服务
供应商服务
交易安全
关注我们
手机网站:
新浪微博:
微信关注:

13520258486

周一至周五 9:00-18:00
(其他时间联系在线客服)

24小时在线客服