字符串匹配 KMP 算法

现在有两个字符串：

str1 = “abcdabbc”

str2 = “cda”

现在请你设计一个 C 语言程序，判断第一个字符串中是否包含了第二个字符串，比如上面的例子中，很明显第一个字符串包含了第二个字符串。

• 暴力解法
• KMP 算法

我们着重来看一下 KMP 算法，实际上我们发现，暴力解法虽然很好理解，但是可能会做一些毫无意义的比较：

当发生不匹配时，又会重新开始比较下一个：

但是我们不难发现，因为不匹配的位置发生在第三个字符，而前面是a,b两个字符都匹配，显然完全没有必要再继续挨着去比较a和b了，因为很明显不可能匹配。

实际上我们可以直接跳过b，因为我们一眼就能看出肯定不匹配，所以直接跳过从后面继续判断，能节省不少的时间。我相信如果让你通过自己的人脑去进行匹配，也是按照这样的方式去比较的吧？

不过关键点就在于怎么在程序中得知该不该跳过呢，又该跳过多少个字符不判断呢？所以我们在拿到子串的时候，就需要根据子串来计算一个叫做next的数组，与子串的长度相同，它存储了当不匹配发生在对应的位置上时，应该在哪一个位置开始继续比较。

这里说一下怎么去求(计算机领域大佬总结出来的算法)：

从第一位开始依次推导。

next 数组的第一位一定是 0。

从第二位开始(用i表示)，将第i-1个字符(也就是前一个)与其对应的next[i - 1] - 1位上的字符进行比较。

如果相等，那么next[i]位置的值就是next[i - 1] + 1

如果不相等，则继续向前计算一次next[next[i-1] - 1] - 1位置上的字符和第i-1个字符是否相同，直到找到相等的为止，并且这个位置对应的值加上1就是next[i]的值了，要是都已经到头了都没遇到相等的，那么next[i]直接等于1。

比如：

首先一二位明确是 0 和 1，这里我们从第三位开始计算，根据我们前面的规则：

1. 首先判断str[next[1] - 1] == str[1]，显然不相等。
2. 此时无法继续向前走了，next[2]直接等于1即可。

我们接着来看第四位：

1. 首先判断str[next[2] - 1] == str[2]，发现相等。
2. 此时next[2]直接等于next[2 - 1] + 1即可。

最后一位也是一样的判断方式：

1. 首先判断str[next[3] - 1] == str[3]，发现相等。
2. 此时next[3]直接等于next[3 - 1] + 1即可。

至此，next 数组求解完毕，之后比较只需要多考虑一下 next 数组即可：

当不匹配发生在第三位时，此时next[2] = 1， 所以我们将第一个元素移动到 c 的位置重新开始比较：

发现不匹配，直接继续向后比较，重复上述操作，像这样这样跳着去比较就大大节省了时间。

OK，理论差不多结束了，上代码。

有关 C 语言的基础部分内容，我们就讲解到这里，从下一章开始，难度将会有一定的提升，所以请各位小伙伴务必将本章知识点梳理清楚，牢记心中。