KMP算法

Knuth-Morris-Pratt字符串查找算法,简称KMP算法,常用语在一个文本串S中查找一个模式串P的出现位置。

算法流程

  1. 假设现在文本串 S 匹配到 i 位置,模式串 P 匹配到 j 位置。
  2. 如果 j=-1,或者当前字符串匹配成功,即 S[i]=P[j],都令i++, j++,继续匹配下个字符。
  3. 如果 j != -1,且当前字符匹配失败(即 S[i] != P[j] ),则令 i 不变,j = next[j]。此举意味着失配时,模式串 P相对于文本串 S 向右移动了 j - next [j] 位。
  4. 换言之,将模式串 P 失配位置的 next 数组的值对应的模式串 P 的索引位置移动到失配处。
Last Updated: 9/20/2019, 4:06:30 PM