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