数据结构和算法回顾-kmp

KMP字符串查找算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。

*此算法的核心是跳过肯定无法匹配的部分，达到高效匹配的目的。 *

这里有一个可能很清晰介绍kmp的blog， 不过没有代码实现，也没有讲原因。

• 那么不高效的匹配是怎样的？
  随便搜到一个暴力匹配算法:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/**
 * 字符串模式匹配 之 BF算法
 * Author : Yonggang Yuan
 */
#define EOS '\0' // End Of String
int main() {
    char text[] = "s a good，Yonggang Yuan is a good student, is a good student twice ... is a good";
    char m[] = "s a good";
    int i, lenOfM = strlen(m);
    for( i=0; *(text+i) != EOS; i++ ) {
        if( memcmp(m, text+i, lenOfM) == 0 ) {
            printf("Match m at %d\n", i);
        }
    }

    return 0;
}

• 前后缀
  一个字符串 ABCABKKJSCNABCAB
  前后缀为: 1)AB 2)ABCAB
  最大前后缀为: ABCAB
• 跳过哪一部分
  移动位数 = 已匹配的字符数 - 对应的部分匹配值
  部分匹配值就是最大前后缀
  下面有两个字符串

串a	A	B	C	A	B	K	K	J	S	C	N	A	B	C	A	B
i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

|串b |A|B|C|A|B|D|F|
|---|-|-|-|-|-|-|-|-|
|j|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|

在a[i=5],b[j=5]时候失配,按照kmp算法，下一步就应该串b就应该向右移动（已匹配数-最大前后缀）,用代码表示就应该为i不变，j=next[j-1]。
怎么理解j=next[j-1]?
next是字符串b的最大前后缀大小值组成的数组,比如子串b[0~5]的最大前后缀为AB,值也就为2,所以next[4]=2。而j=next[j-1]就表示j的下标变为b[j]前面的字符串的最大前后缀,

上面这个例子可以用下图表示

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
串a	A	B	C	A	B	K	K	J	S	C	N	A	B	C	A	B
串b				A	B	C	A	B	D	F
j				0	1	2	3	4	5	6	7

从i[5],j[2]开始重新匹配,相对于暴力匹配法跳过i[1_2],由于i[34]与j[0~1]必然相等,也被忽略。

为什么i[1~2]可以直接跳过,会不会从i[1],j[0]开始直接匹配上了，那我来看看这情况，如下图

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
串a	A	B	C	A	B	K	K	J	S	C	N	A	B	C	A	B
串b		A	B	C	A	B	D	F
j		0	1	2	3	4	5	6	7

因为在i[5],j[5]处失配,所以i[5]应该和什么匹配未知，已知的条件不能判断，而用已知条件只要证明i[1_4]与j[03]绝对不匹配就行了，
已知条件:
1)i[0_4]与j[04]已经匹配上了
2)next数组(看做已知的,后面在详细求解)
如果上图的情况能匹配上，那么i[1_4]=j[03],又已知i[1_4]=j[14],所以j[0_3]=j[14]所以j[0_3]和j[14]是j[0_{4]的前后缀,然而ABCAB的最大前后缀是AB值为2,已经矛盾了，所以i[1}4]与1[0~3]绝对不匹配，可以跳过。

• next数组
  next[k]也就是字符串b[0~k]的最大前后缀，数组求法有点像数学归纳法，首先我们知道next[0]=0,然后递归求取next[1],next[2]...next[n]。
  一步步来看,先判断b[1]和b[0]是不是相等，如果相等那b[0],b[1]就为b[0~1]的前后缀

• golang代码实现

func KmpMatch(astring string, bstring string) int {
        i, j := 1, 0
        next := make([]int, len(bstring))
        next[0] = 0
        for i < len(bstring) {
                if bstring[i] == bstring[j] {
                        next[i] = j + 1
                        i++
                        j++
                } else if j == 0 {
                        next[i] = 0
                        i++
                } else {
                        j = next[j]
                }
        }
        i, j = 0, 0
        for i < len(astring) {
                if astring[i] == bstring[j] {
                        if j == len(bstring)-1 {
                                return i
                        }
                        i++
                        j++
                } else {
                        if j > 0 {
                                j = next[j-1]
                        } else {
                                j = 0
                                i++
                        }
                }
        }
        return 0
}