面试题：写一个在一个字符串(n)中寻找一个子串(m)第一个位置的函数。 10+G的日志中，如何快速地查找关键字？
对于字符串abcabcabcabcd，子串abcabcd

暴力匹配算法如下：每一次发现子串不匹配，将子串后移一格并从第0个字符开始重新匹配

但其实肉眼观察一下不难发现应该这样匹配，

如果匹配不成功，我们应该将子串往后移动3位而不是1位，并且在子串的第3个字符’a’（这个3表示下标，从0开始）与主串的当前字符进行匹配，至于为什么是子串的第3个字符开始与主串匹配而不是像暴力那样重新从第0个字符重新匹配，这里我们是用肉眼观察法观察所得的，但其实是有一个严谨的过程推算得到的，下面我们先引入两个概念，前缀与后缀

前缀：除了最后一个字符，一个字符串的全部头部集合

后缀：除了第一个字符，一个字符串的全部尾部集合

前缀一般不会搞错，但是注意后缀集合，从后往前看，逐个选取组合，比如abcabc的后缀集合{c，bc,abc,cabc,bcabc}，不要搞错了

为什么子串abcabcd匹配到第7个字符”d”发现不匹配时，这个时候已经匹配成功的模式串是”abcabc”，这个时候我们寻找到”abcabc”的最长相等前后缀是abc，子串移动的结果是让子串的最长相等前缀和主串最长相等后缀对齐，这也就是为什么需要将子串移动3位而不是像暴力那样移动1位。

前后缀的对齐操作

而我们子串重新开始匹配的字符的下标应该是3而不是0，（这个下标3和上面的子串移动位数3相等只是一个巧合）而这个下标3正是最长相等前后缀的长度。所谓的子串回溯后应该对应的字符的下标就是最大公共前后缀的长度。而注意我们的主串的字符下标指针是永远不会回溯的，不会往前走（这区别于暴力算法），只会一直执行i++操作；只有子串的字符下标可能会执行回溯操作

这里我们将最大公共前后缀长度那一列的集合记为next数组

一是之前提到，next[i]的值表示下标为i的字符前的字符串最长相等前后缀的长度。

二是：表示该处字符不匹配时应该回溯到的字符的下标

下面我们的问题变为了应该如何求取next数组呢？

再看看一看这幅图，next数组求取一定是从上往下求取的，因为之后涉及一个k = next[k-1]的操作，正是因为有这个操作，太难以明白kmp算法了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void make_next(const char *pattern, int *next) {

    int j, k;
    int m = strlen(pattern);

    next[0] = 0; // 
    for (j = 1,k = 0;j < m; j ++) {

        while (k > 0 && pattern[j] != pattern[k]) {
            k = next[k-1];
        }

        if (pattern[j] == pattern[k]) { // 如果前缀与后缀有相同的字符
            k ++;
        }

        next[j] = k;
      
    }
}

首先解释这个j，k变量，这两个是用来表示后缀与前缀的范围，

先不看while循环，看这个if循环

1
2
3
4
if (pattern[j] == pattern[k]) { // 如果前缀与后缀有相同的字符
      k ++;
}
next[j]=k;

就只有这么一句如果前缀与后缀有相同字符，那么k++，前缀的范围可以加大，并且接着执行next[q]=k；next[q]的值也增加

再看那个while循环

1
2
3
while (k > 0 && pattern[j] != pattern[k]) {
    k = next[k-1];
}

特别注意灰色部分是红色字符串的最长相等前后缀，因此后面红色部分的灰色区域与前面的灰色区域保持一致

判断当前位置data[j]和前面那一块灰色data[k]是否相等。如果这两位相同的话，就可以和前面的灰色部分连在一起成为新的相等最长前后缀，这就是k=next[k]的含义了。

解决了next数组的初始化，剩下的KMP算法就容易了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int kmp(const char *text, const char *pattern, int *next) {

    int n = strlen(text);
    int m = strlen(pattern);

    make_next(pattern, next);

    int i, q;
    for (i = 0, q = 0;i < n;i ++) { //i --> text, q --> pattern

        while (q > 0 && pattern[q] != text[i]) {
            q = next[q-1];
        }

        if (pattern[q] == text[i]) {
            q ++;
        }
        // q == m --->  
        if (q == m) {
            return i-q+1;
        }
    }
    return -1;
}

注意i是主串的下标指针，一直执行的i++操作不会回退，这是相对暴力的第一个优势，另外q是子串的下标指针，如果不匹配会通过next数组回退到应该回退的位置，而不是像暴力一样直接回退到第0个字符，这是kmp相对暴力的第二个优势