KMP 算法的实现详解
@TOC
1.KMP 算法
1.概念
KMP 是一种改进的字符串匹配算法,该算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。 具体实现通过一个 next()函数实现,函数本身包含了模式串的局部匹配信息。
2.与 BF(暴力算法)的的区别
暴力算法:模拟实现strstr函数当信息匹配失败时,主串 i 不会回退,子串 j 也不会回到 0 号位置
3.分析
1.j 的回退位置
在下标为 5 时,信息匹配失败,此时 i 不回退,在此匹配失败,说明 主串 i 与子串 j 下标 5 之前一定有一部分是相同的,此时 j 回退到 下标为 2 的位置,继续向后就能匹配成功。
2.next 数组
next[j]=k 来表示,不同的 j 对应一个 k 值,k 为要移动的 j 要移动的位置
寻找 k 规则:1.匹配成功部分的两个相等的真子串(不包含本身),一个以下标 0 开始,另一个以 j-1 下标开始结尾。2.规定 next[0]=-1 ,next[1]=0, 正式计算是从下标 2 开始。
3.next 数组的练习
1.练习 1
注意事项
2.练习 2
注意事项
一个小细节:一般来说 next 数组下标 只会一个一个数加 或者被赋值成 0
4.推导过程
在 next[i]=k 的前提下
1.p[i]==p[k]
在 p[0]......p[k-1] p[i-k]==p[i-1] , next[i]=k 的前提下....p[0]......p[k-1] p[k] == p[x]...p[i-1] p[i] , next[i+1]=k+1
2.p[i]!=p[k]
回退到下标为 2 的位置,发现此时 p[i]!=p[k],则从当前位置继续回退,直到 p[i]==p[k],再通过 next[i+1]=p[k+1], 确定 p[i+1]对应的 next 下标数
4.代码实现
1.代码的注意事项
1.next 数组值为-1 时
当此时的 p[i]!=p[k]时,一直通过 next 数组值返回到前面的 p 所在,但到第一个数依旧 p[i]!=p[k]时,则会将 k 置成-1,进入 if 循环后 k 值为 0 即 此位置的 next 所在下标为 0
2.k 值为-1 时
只有第一个数对应 next 数组的值为-1,说明主串与子串第一个数就信息匹配失败而在 if 循环中如果不加入 j==-1 的判断 ,只有 sub[i]==sub[j],则会造成越界
2.KMP 算法的优化
关于 next 数组的优化
若在下标为 5 的位置信息匹配失败,就会一直回退,直到下标为 0 的位置优化的目的就会使 此时直接找到下标为 0 的位置
1.规则
如果回退到的位置和当前字符一样,就写回退那个位置的 nextval 值如果回退到位置和当前字符不一样,就写当前字符原来的 nextval 值
评论