KMP算法独门秘籍（面试问到就这么回答）_kmp算法面试会问吗

介绍
字符串匹配历来都是面试中比较高频的题。而字符串匹配的算法也有很多种，今天我们讲解的是传说中的KMP算法。学过算法导论的朋友应该对这个不陌生，在算法导论字符串匹配章节对KMP算法有着很详细的讲解，但我们总不能面试时去照着算法导论讲的原理读吧，那样面试官估计都能被你催眠了^-。那我们今天就挑其中的重点难点来讲一下KMP算法。
想了解其他字符串匹配算法的朋友倒是可以去拜读一下算法导论，可以拓宽你解决问题的思路。

原理
KMP算法的重中之重其实就是两个字，回溯。通过回溯的方法找到模式串下一次移动的位置，最终完成字符串的匹配。这样可以尽可能少的降低模式串移动的次数。

算法详解
再详细说明算法实现之前，我们来熟悉一下两个后面用到的概念，前缀和后缀。前缀按照我的理解就是从第一个字符开始，往后递增，得到的子串就是一个前缀。后缀就是从后往前递增。
举个例子：
ababa
前缀：a ab aba abab（注意，前缀最多是到倒数第二个字符，如果是最后一个字符也包含那不就是完整的字符串吗）
后缀：a ba aba baba（后缀也是不能包含第一个字符）
通过观察模式串和的匹配过程我们可以发现，当我们遍历到有字符不等时，不用苦逼的每次都移到主串的下一个字符从头再来。我们只要稍微观察下模式串已经和主串匹配的部分。由于已匹配的部分肯定是和主串相等的，那么只要直接移到模式串前后与后缀匹配的前缀部分。这么说可能比较抽象，上图：

上图移动，指向模式串的指针j实际是转移到了公共匹配前缀的下一个字符。这样每次可以减少很多次匹配的消耗，大大提高了效率。
既然上面的方法是很实用，但我们怎么知道每次怎么移动，该移动到哪个字符呢？我们能想到的是，在某个地方记录下每次要移动的位置，等到符合条件的时候我们再把它拿出来，那么这时候就引出了传说中的next数组。这个数组里存放的是每个前缀与后缀公共匹配的长度，这样有了这个法宝，每次移动只要拿出匹配的长度就知道移动多少的匹配长度了。
下面来讲讲next数组的合成。其实图解的话会很简单，无非就是比对一下前后缀的最长匹配的长度记到数组里面。还是以ababa为例吧。它的next数组的值分别为0 1 0 3 0。下面我们来看下代码怎么实现的吧。首先第0位我们使用不到的，肯定是0，因此从第一位开始求数组。

void getNext(const char *pattern, int *next, int plen)
{
    int i, j;
    next[0] = 0;
    for (i = 0; i < plen; i++) {
	    while (j > 0 && patter[j] != pattern[i]) {
		    j = next[j - 1];  // i 和 j都是指向匹配串的下一个字符
		}
		if (pattern[i] == pattern[j]) {
		    j++;
		}
		next[i] = j;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

以上就是求next数组的代码，i指向的是匹配字符串的下一个位置，j指向的是匹配最长公共前缀的下一个位置。其中比较难理解的是j = next[j - 1]，上文我们通过图描述过，当我们遇到不匹配的情况是j移动到对应next数组中的值的位置，这次实际上是对匹配字符串本身做了一次回溯，找到他的前一个公共匹配的最长前缀。
下面我们就贴处KMP算法的代码：

int KMP(char *str, char *pattern)
{
    int slen = strlen(slen);
    int plen = strlen(plen);
    int i, j;
    int *next = new int[plen];
    if (next == NULL) {
		return;
	}
	getNext(pattern, next, plen);
    for (i = 0，j = 0; i < slen; i++) {
		while (j > 0 && pattern[j] != str[i]) {
			j = next[j - 1];
		}
		if (pattern[j] == str[i]) {
			j++;
		}
		if (j == plen) {
            return i - j + 1;
        }
	}
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

上述代码描述，如果找到第一个匹配的字符串，那么就返回匹配的第一个字符的位置，否则返回-1。
KMP算法的核心部分就是这些，如有错误，望指正。