算法

KMP算法简述

最近在考虑优化一些字符串匹配的方式,但是golang本身有标准库实现,看了下实现,在一定字符长度中会用到RK算法,去搜索了解了下RK算法后,看到kmp的算法,学习实现了一版。

一般判断两个字符串是否相等,是需要每个字符一一比较,最后得出结论相等,复杂度为o(n)。如果需要判断字符是否串包含的关系,暴力的情况会出现比较高的复杂度。而导致出现较多的复杂度的原因,是有个重复比较的过程,下面举例说明一下

例如:

pattern: aaab
text:    aaaaaab
a a a a a a b
a a a b

匹配了三位之后,不等,pattern往后移动一位,继续比较,注意前面说过,比较是需要字符一一进行比对。

a a a a a a b
a a a b

不等,重复上面的动作并匹配,直到最后一位确定相等。

a a a a a a b
a a a a b

可以看出暴力的匹配方式,最坏的情况是o(mn),也很明显可以看到存在重复比较,但是哪些是可以忽略不做比较的呢,为了方便理解前后缀,修改一下pattern和text的示例。

pattern:  abcabc
text:    abcababcabc
a b c a b a b c a b c
O O O O O X
a b c a b c

如果往后移动一位继续匹配的话,可以看到

a b c a b a b c a b c
X
a b c a b c

可以看到bcabab对于abcabc压根不可能匹配上,只有在前缀与后缀有相同的情况下,才有机会相等。

a b c a b a b c a b c
O O X
a b c a b c

也就是移动到上述位置。

不知道上述例子有没有帮助理解前后缀的作用,其实kmp算法主要就是算出前缀表,因为前后缀有相等的,移动位置可以减少不必要匹配,否则就从pattern开始位置开始匹配,下面来尝试求next数组。

对于前后缀表,要求出其对应的前后缀的最长公共子串长度,对于前后缀,例如abc的前缀就是ab,后缀就是bc。h还是相同的pattern例子。

子串 前缀 后缀 公共长度
a - - 0
ab a b 0
abc ab bc 0
abca abc bca 1
abcab abca bcab 2
abcabc abcab bcabc 3

所以求出next数组为[0,0,0,1,2,3]

下面来走一遍kmp搜索的流程

pattern:  abcabc
text:    abcababcabc
a b c a b a b c a b c
O O O O O X
a b c a b c
i = 5,j = 5,此时匹配错误,j = next[j-1],也就是 j = next[4],j = 2
a b c a b a b c a b c
O O X
a b c a b c
i = 5, j = 2,匹配错误,继续,j = next[j-1] = next[1] = 0
a b c a b a b c a b c
O O O O O O
a b c a b c

可以看到上述流程,即为kmp的整个搜索流程,最坏的情况,也就o(m+n)

Leave a Reply

Your email address will not be published.

16 − twelve =