目录
KMP算法的介绍
详解KMP算法
next数组的填充
代码实现
KMP算法的介绍
KMP算法是解决字符串匹配问题的一个经典算法，字符串匹配问题就是查找子串T是否在主串S中存在，其中在KMP算法中，主串也被称为目标串，子串也被称为模式串。
而在认识KMP算法之前，我们可以先认识BF算法，这是一个简单粗暴的算法：从主串开始逐个对比，成功找到就停止，并进行一系列操作，没有找到就回溯，直到主串走到最后为止。图例如下：
可以说， BF算法的问题是由目标串（主串）决定的，因为在BF算法的过程中，是目标串的下标在不断移动，而模式串只是被动的去和目标串匹配。而在KMP算法中，问题是由模式串决定的，而不是目标串，这么做可以大大提升字符串匹配的效率。例如在上方的例子中，KMP算法是直接跳过了其第二趟、第三趟，直接来到了第四趟，因为前两个字符是相等的，再匹配的意义以及不大了。如下图所示：
如果我们假定目标串的长度为m，模式串的长度为n，那么BF算法的时间复杂度是O(mn)的（因为需要不断回溯），但KMP算法的时间复杂度是O(m+n)。至于KMP算法到底是怎么回事呢？还请继续阅读下面的部分。
详解KMP算法
在KMP算法中，一个关键内容就是next数组，next数组的内容是与模式串的内容一一对应的，next数组中存放的是一个个整型元素，这些整型元素的意义代表：如果当前位置模式串的字符与目标串的不匹配，那么模式串的下标就跳转为这个整型元素。以上面“ABCABA”的字符串为例：
至于这个next数组的内容是怎么来的会在下一个内容板块详细讲解，这里先假定存在这个next数组，那么在此条件下KMP的过程如下：
所以这也就算是为什么说KMP算法的的问题是由模式串决定的，KMP中主要是对模式串进行操作，而主串基本上是“不动”的。在已知next数组的条件下执行KMP的代码如下：
int KMPSeek(char* String, char* SubString)
//字符串匹配，找到了就返回所在主串位置的下标，没找到就返回-1
{
int lenS = strlen(String); //目标串的长度
int lenT = strlen(SubString); //模式串的长度
int next[255];
InitNextArray(SubString, next); //填充next数组（这里先不用管）
int subscript = -1; //返回的下标
int i = 0, j = 0;
while (i < lenS)
{
if (j == 0) //更新下标
subscript = i;
//子串与主串字符比较
if (j == -1 || SubString[j] == String[i])
i++, j++; //逗号运算符。
else
j = next[j];
//检测是否完成匹配
if (j == lenT - 1 && SubString[j] == String[i])
{
printf("找到了，下标是：%d\n", subscript);
return subscript;
}
}
//走出循环就一定是没找到
puts("404 Not Found!");
return -1;
}next数组的填充
要知道，KMP算法的重点和难点就是next数组。
在学习如何填充next数组之前我们还需要了解 “最长公共前后缀” 这么一个概念，其实这并不是一个多么复杂的概念我们这里简单介绍一下，前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。所以最长公共前后缀就是字面意思了。以“ABCAB“这么一个字符串为例，其前缀有 {{A}, {AB}, {ABCA}} 这么几个，后缀有{{B}, {AB}, {CAB}, {BCAB}} 这么几个,那么最长公共前后缀就是”AB“，其长度为2。
了解了什么是最长公共前后缀之后，我们再来看next数组，next数组的内容存放的就是从下标为0的位置开始直至当前下标的前一个元素的位置（即从下标为0至下标为i-1的字符串）这个字符串的最大公共前后缀的长度。
那么接下来该这么求其最长公共前后缀呢？首先设置两个整型变量i，j（实质就是数组下标，i为前缀下标，j为后缀下标），起初i为-1，j为0，然后分别让其加一，即i为0，j为1。然后开始我们的填充过程，先判断i位置的字符是否相等，相等就使i和j同时后移，然后让此时的next[j]等于i，如果不相等就j不动i赋值为next[i]，这个过程很像KMP的过程。然后循环往复，直至j走到最后。
这里总结一下填充next数组的核心思路：
1 - 前缀是固定的，后缀是相对的
2 - 填充next的过程就是“以存在的前后缀最大公共部分为字串，以0到后缀的位置为主串”，不断进行“自身KMP”的过程
具体的过程示例图解如下，以字符串”abxabwabxad“为例
代码实现
#include<stdio.h>
#include<string.h>
void InitNextArray(const char* SubString, int* next) //填充next数组，next数组存放的是失配时跳转的数组下标
{
/*
填充next数组的核心思路：
1 - 前缀是固定的，后缀是相对的
2 - 填充next的过程就是“以存在的前后缀最大公共部分为字串，以0到后缀的位置为主串”，不断进行“自身查找”的过程
*/
//puts(SubString);
int lenT = strlen(SubString);
next[0] = -1; //
int i = -1, j = 0; //i是前缀指针，j是后缀指针
while(j < lenT)
{
if (i == -1 || SubString[i] == SubString[j])
{
/*next[++j] = ++i; //未优化，不能高效处理重复字符 */
//优化后的做法
if (SubString[++i] == SubString[++j]) //i,j加一后再次对比，减少跳转次数
next[j] = next[i];
else
next[j] = i;
}
else
{
i = next[i];
}
}
}
int KMPSeek(char* String, char* SubString) //字符串匹配，找到了就返回所在主串位置的下标，没找到就返回-1
{
int lenS = strlen(String); //S串的长度
int lenT = strlen(SubString);
int next[255];
InitNextArray(SubString, next);
int subscript = -1; //返回的下标
int i = 0, j = 0;
while (i < lenS)
{
if (j == 0) //更新下标
subscript = i;
//子串与主串字符比较
if (j == -1 || SubString[j] == String[i])
i++, j++;
else
j = next[j];
//检测是否找到
if (j == lenT - 1 && SubString[j] == String[i])
{
printf("找到了，下标是：%d\n", subscript);
return subscript;
}
}
//走出循环就一定是没找到
puts("404 Not Found!");
return -1;
}
int main()
{
char strS[] = "nmiucowabcooxx"; //S串 - 主串
char strT[] = "abc"; //T串 - 子串
KMPSeek(strS, strT);
return 0;
}
