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类型变量,即可成功输出
补全绿色注释。