KMP算法目的:尽快解决字符串匹配问题,时间复杂度为O(m+n),而常规的简单匹配算法时间复杂度:O(m*n)
这个算法不太容易理解,而且网上很多关于KMP算法的文章读起来很费劲,以下,我按照自己的理解,试着写一篇易懂的算法解释。
1 关于模式的前后缀函数(next数组获取)
首先,为了方便后面的描述,先定义下:S表示原字符串,T表示目标字符串(模式串),关于字符串匹配,就是在S中寻找T。
关于寻找字符串的前后缀,举个例子:
字符串:abcab
前缀:a,ab,abc,abca
后缀:bcab,cab,ab,b
“前缀”指除了最后一个字符以外,一个字符串全部头部组合。
“后缀”指除了第一个字符以外,一个字符串全部尾部组合。
模式前后缀函数,就是产生一个长度等于模式串T长度的数组,每个值为相应“部分匹配值”的数组。
“部分匹配值”就是“前缀”和“后缀”的最长的共有元素字符串的长度。以“ABCDABD”为例:
模式串 | A | B | C | D | A | B | D |
---|---|---|---|---|---|---|---|
部分匹配值(next) | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
- "A"的前缀和后缀都为空集,共有元素的长度为__ 0 __;
- "AB"的前缀为[A],后缀为[B],共有元素的长度为__ 0 __;
- "ABC"的前缀为[A, AB],后缀为[BC, C],共有元素的长度__ 0 __;
- "ABCD"的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为__ 0 __;
- "ABCDA"的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为"A",长度为__ 1 __;
- "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为"AB",长度为__ 2 __;
- "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为__ 0 __。
所以,对于字符串"ABCDABD",会相应地产生一个数组array(0, 0, 0, 0, 1, 2, 0)。这就是KMP算法关于next数组(也就是计算前后缀函数)原理,它记录的是模式串T子串(T[0 ... j] 0 < j < n)的最长前后缀元素长度的信息。
接下来,介绍KMP算法思想。
2 KMP算法思想
第一次:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
---|---|---|---|---|---|---|---|---|---|---|---|
S | a | b | c | a | b | c | a | b | d | a | |
T | a | b | c | a | b | d | |||||
0 | 1 | 2 | 3 | 4 | 5 |
第二次:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
---|---|---|---|---|---|---|---|---|---|---|---|
S | a | b | c | a | b | c | a | b | d | a | |
T | a | b | c | a | b | d | |||||
0 | 1 | 2 | 3 | 4 | 5 |
传统匹配算法中,每一轮匹配过后,都会回溯到T[0]和S[i+1]的状态位置开始下一轮的匹配。而上面的表图运用了KMP算法,显然两次就能得出匹配信息:
这里先给出模式串T("abcabd")的next数组参照:
模式串 | a | b | c | a | b | d |
---|---|---|---|---|---|---|
部分匹配值(next) | 0 | 0 | 0 | 1 | 2 | 0 |
0 | 1 | 2 | 3 | 4 | 5 |
第一个表格中,S[5]与T[5]匹配失败时,T[0 ... 4]字符串最长“前-后缀”是"ab",它在T[0 ... 4]中对应的前缀是T[0 ... 1],后缀是T[3 ... 4] (前后缀相等),既然T[0 ... 4]与S[0 ... 4]匹配成功,那么T[0 ... 1]必然与S[3 ... 4]完全匹配。(先结合next获取那段好好理解)
由此可以想到,当S[i]与T[j]匹配失败时,如果我们知道T[0 ... j-1]最长“前-后缀”在T[0 ... j - 1]对应的前缀是T[0 ... m] (m = next[j-1] - 1),那么我们可以直接将S[i]与T[m+1]对齐,开始下次匹配,因为T[0 ... m]必然已经与S[0 ... i - 1]的后缀匹配成功。避免了不必要的回溯
下面是KMP算法代码:
def `kmp-matcher` (s: String, t: String): Int = {
val next = `init-next`(t)
val s_len = s.length
val t_len = t.length
var i = 0 /*记录原字符串下标*/
var j = 0 /*记录模式串下标*/
while (i < s_len && s_len - i > t_len - j) {
while (j < t_len /*注意先检查下标越界*/ && s.charAt(i) == t.charAt(j)) {
i = i + 1
j = j + 1
}
/*
* 下面有两种分支,完全匹配和匹配中断
* 完全匹配:函数直接返回匹配时的坐标
* 匹配中断:设置i,j下标,使其S[i]与T[NEXT[j-1]]对齐,进行下一次匹配
*/
if (j == t_len /*完全匹配,此处直接返回此次匹配首位下标*/)
return i - t_len
else /*匹配中断*/
j = next(j match {
case 0 => i = i + 1; j/*无“前-后缀”,直接将i下标加一匹配*/
case _ => j - 1
})
}
-1 /*无匹配项*/
}
上述代码缺少\
init-next` `函数的实现,也就是next数组的获取:
实际上,next数组记录的是模式串T的各个字串C[0 ... j] (0 < j < T.length)的最长“前-后缀”长度信息。
传统暴力求解next数组显然很低效,这里也运用KMP匹配的方法获取next数组。也就是在模式串T自身上使用KMP匹配:
用两个变量i和j扫描T,i将模式串看做S,j将模式串看做T。每次增加i时,赋予next[i]合适的值,也就是最长“前-后缀”的长度。
def `init-next` (s: String): Array[Int] = {
val len = s.length
val next = new Array[Int](len)
next(0) = 0 //首个元素最大前后缀元素:无,所以此处设置为0
var i = 1
var j = 0
while (i < len) {
if (s.charAt(i) == s.charAt(j)) {
j = j + 1
next(i) = j
i = i + 1
} else if (j == 0) {
next(i) = j
i = i + 1
} else {
j = next(j - 1)
}
}
next
}