首页 > 代码库 > 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算法