KMP算法

什么是KMP算法

KMP算法是带有跳跃性的字符串匹配算法。具体请参考百度百科


什么是next数组

next[ind]表示模式串Pattern的Pattern[0...ind]子串注释1最长公共前后缀的长度。其中,next[0] = 0。
值得注意的是:在计算next数组的时候,可以根据前一个字符的next值,计算后一个字符的next值。
kmp-1
也就是说,当Pattern[ind] 等于 Pattern[j]的时候,next[ind] = j + 1。
否则:
kmp-2
当Pattern[ind] 等于 Pattern[k]的时候,next[ind] = k + 1,否则判断Pattern[ind] 是否等于 Pattern[next[k-1]],。。。,以此类推,一直到某个字符的next值为0。


模式匹配

kmp-3
假设主串的MainString[i-j...i-1] 和 模式串的Pattern[0...j-1]匹配,而MainString[i] 和 Pattern[j]失配,此时,就需要回溯
在KMP算法中,回溯到的位置不是 i - j + 1,而是:
kmp-4
这就是本文开头所说的跳跃性。


代码实现

tim-chow/DataStructure


注释

  • 注释1:S[x...y]表示字符串S的索引从x到y的子串(包含x,y)

感谢浏览tim chow的作品!

如果您喜欢,可以分享到: 更多

如果您有任何疑问或想要与tim chow进行交流

可点此给tim chow发信

如有问题,也可在下面留言: