字符串匹配-KMP算法
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
}
