首页 > 代码库 > KMP算法

KMP算法

针对字符串匹配问题:

  暴力的匹配方式莫过于,从前到后,一一对比判断,从长度为n的目标串(记:target),匹配到长度为m模版串(记:pattern)

  时间复杂度为O(m*n)

KMP算法:

  KMP算法则不用一步步的向前移动匹配,可以计算出一个next数组(跳转表),快速的匹配。

  计算next的复杂度为m,运用next表对目标字符串匹配的复杂度为n

  时间复杂度为O(m+n),效率提高极为显著

KMP算法匹配过程:

  1.求出next,next表是根据pattern来求,考虑到是模版字符串中,最大相等字符子串的长度,String pattern="abcabcacab"; 这里拿出经典的字符串来计算并说明:

技术分享

  next计算方式,红色字符表示要计算的子字符串,依次算出patten的十个跳转数字(提示:后面匹配过程中,匹配失败后,前移的长度为:匹配失败的index-next)

  技术分享  前后缀最大相等字符子串的长度=0

  技术分享  前后缀最大相等字符子串的长度=0

  技术分享  前后缀最大相等字符子串的长度=0

  技术分享  前后缀最大相等字符子串的长度=1

  技术分享  前后缀最大相等字符子串的长度=2

  技术分享  前后缀最大相等字符子串的长度=3

  技术分享  前后缀最大相等字符子串的长度=4,注意:abca

  技术分享  前后缀最大相等字符子串的长度=0

  技术分享  前后缀最大相等字符子串的长度=1

  技术分享  前后缀最大相等字符子串的长度=2

   2.匹配:目标字符串String target="babcbabcabcaabcabcabcacabc";  向前移动的距离为pattern的index-next,(注:index的起始为1)

技术分享

 

 

 

 

   

 

KMP算法