功能：在大字符串里找小字符串

主串：“ABABCABCDABCDE”
子串：“ABCD”
在主串里面找子串

BF算法：枚举法（暴力求解）

思想：把所有可能列出来 一个一个去尝试
逻辑：
1.申请两个变量i和j
2.让变量i指向主串的开始字符位置，让变量j指向子串的第一个字符位置
3.进入while，循环条件是i和j都还合法
4.进入后比较i和j指向的字符
5.如果i和j指向的字符相同 则让i和j同步向后走一步
6.如果i和j指向的字符不同 则让j回退到0号下标的位置 i也要回退到这一次失败匹配的开始位置的下一个字符
7.当while循环结束 我们去判断j是否越界 如果j越界说明查找成功 返回i-j 如果失败返回-1

1.当while循环结束 判断是否查找成功只和变量j有关系 和i没有关系

2.查找成功时为什么返回i-j?

查找成功时 只需要让变量i减去i和j共同走过的距离即可 此时i就回到了这一次成功匹配的开始位置

具体逻辑：

BF算法：start是光标位置 表示主串从哪一个位置开始向后找

int BF_Search(const char* MainStr,const char* SubStr,int start)
{
	//1.申请两个变量i和j
	//2.让变量i指向主串的开始字符位置，让变量j指向子串的第一个字符位置
	int i=start;
	int j=0;
	//3.进入while，循环条件是i和j都还合法
	while(i<(int)strlen(MainStr)&&j<(int)strlen(SubStr))
	{
		//4.进入后比较i和j指向的字符
		//5.如果i和j指向的字符相同 则让i和j同步向后走一步
		if(MainStr[i]==SubStr[j])
		{
			i++;
			j++;
		}
		//6.如果i和j指向的字符不同 则让j回退到0号下标的位置 i也要回退到这一次失败匹配的开始位置的下一个字符
		else
		{
			i=i-j+1;
			j=0;//i要放在j回退代码之前
		}
	}
	//7.当while循环结束 我们去判断j是否越界 如果j越界说明查找成功 返回i-j 如果失败返回-1
	if(j<(int)strlen(Substr))
		return -1;
	return i-j;
}

测试程序：

结果：

KMP算法：

BF算法
优点：思路简单 代码简单
缺点：效率低 时间复杂度高
KMP算法：充分利用事先准备的信息(Next数组) 从而可以让指向主串字符的变量i在发生失配现象时 可以保证不回退 从而让效率可以达到O(n+m)
核心：变量i打死不回退

场景一：

如果发生失配时 从字串的失配位置向前看 可以找到两个真字串 一个顶头开始 一个顶尾结束且相等且最长最长公共前后缀

保证i可以不用回退

首先 通过已知条件可以得到 子串的失配位置向前看 可以找到最长公共前后缀 一定存在左绿=右绿

其次 当发生失配现象时主串和子串已经经过的部分一定是一模一样的 则一定存在上红=下红

最后 既然上红=下红 则截取上红和下红共同的一个部分 则截取下来的上橙=下橙

总结：因为上橙=下橙 又因为下橙=右绿 又又因为左绿=右绿 则可推出左绿=上橙

因为上橙=左绿 则如果发生失配时 为什么i不用回退？

此时i指向第四个字符A时 有价值 但是紧接着i从这个有价值的位置继续向后走 再次走到原本回退之前的位置，所经过的路径刚好就是“上橙” 同理子串变量j配合变量i的回退 回退到了0, 同一时间内j接下来要走的路径刚好是“左绿”
又因为 事先已经知道 “左绿=上橙” 则默认i回退了 并且将这一段路径走完了(j需要回退到一个合适的位置 不能回退到0)

j的回退位置：

总结：子串从失配位置向前看 如果可以找到最长公共前后缀 则可以让i不用回退(这种情况下 i的回退要么无意义 要么可以让j回退到一个合适的位置 从而抵消掉)

场景二：

如果发生失配时 从字串的失配位置向前看 找不到最长公共前后缀 i也可以不用回退

为什么i可以不用回退？

为了配合主串i的回退 子串j已经回退到0号下标了 此时i回退的位置 要么没意义(一开始第一个字符都匹配不上) 要么有意义 但是接下来i从这个位置出发走到回退之前的位置所经过的路径 一定不等于同一时间内j走过的路径 所以i这种情况下也是没有意义的回退
总结：子串从失配位置向前看 如果找不到最长公共前后缀 则这种情况下i也可以不用回退
场景一和场景二结合 则i无论如何都不用回退
所以KMP的核心 只和子串有关系 跟主串没太大关系 其核心是求NEXT(next)数组
因为子串的任何一个字符都可能发生失配现象 则每一个字符都会有一个合适的回退下标 那么将每一个字符的回退下标统一用一维数组保存 这个数组就是KMP最核心最核心的NEXT数组
与BF算法相比较大大节省时间提高效率
BF的匹配过程:

KMP的匹配过程:

NEXT数组无论什么子串他的前两位一定是-1 0 NEXT数组的第一个字符的next值是固定的-1 这个-1是当作越界的标记 一旦j回退到-1 就代表此时j退无可退 换句话说就是此时主串中的i太特殊了 子串再怎么回退都匹配不上 应该让主串的i向后走一步把这个特殊字符跳过去然后再接着比较

ABABCABCDABCDE
1 001 2012 001 200
具体操作步骤：
1.申请一个next数组 长度和子串长度一致
2.将前两个格子直接赋值为-1和0
3.定义一个变量k 用来保存当前的最长公共前后缀长度
4.进入for循环 通过变量j从第二个字符出发 向后走 也就是用j指向最新的已知字符来推理下一个字符的合适的回退位置
5.如何推理？ 如果当前j指向的字符和回退位置的字符相同 则让k+1赋值给下一个字符 然后让j和k同步向后走
6.如果当前j指向的字符和其回退位置的字符不相同 则让k=Next[k] 然后j和其回退位置的字符的回退位置(k)去比较 如果比较成功了 让当前k+1赋值给下一个字符 然后让j和k同步向后走一下
7.如果一直回退一直失败 (一直让k=next[k])一直让k回退到了-1 就代表k已经触底了 则让k+1重新变成0赋值给下一个字符 然后k和j同步向后走一步
当for循环结束 整体next数组赋值结束
代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* Get_Next(const char* SubStr)
{
	//1.申请一个next数组 数组长度=子串长度
	int n = strlen(SubStr);
	int *next = (int*)malloc(n * sizeof(int));
	if (next == NULL)
	{
		exit(EXIT_FAILURE);
	}
	//2.申请一个变量k 用来保存当前最长公共前后缀的共有长度
	int k = 0;
	//3.将next数组的前两个位置直接赋值为-1和0
	next[0] = -1;
	next[1] = 0;
	//4.进入循环 循环让j从第二个字符出发 到倒数第二个字符停止
	int j = 1;
	while(j<n-1)
	{
		//5.进入后 用j指向的字符和其回退的字符比较有三种可能性
		//5.3第一次比较失败 然后让j和其回退字符的回退字符next[K]进行比较 一直回退一直失败 直到k回退到-1代表触底了=》k+1变成0 再赋值给下一个位置
		if (k == -1)
		{
			next[j + 1] = k + 1;
			j++;
			k++;
			continue;
		}
		//5.1第一次比较直接成功 =》k+1赋值给下一个位置
		if (k ** -1 || SubStr[j] ** SubStr[k])
		{
			next[j + 1] = k + 1;
			j++;
			k++;
		}
		else//5.2第一次比较失败 然后让j和其回退字符的回退字符next[K]进行比较 直到成功
		{
			k = next[k];
		}
	}
	//7.当循环进不去了 代表着next数组的所有位置都赋值完了
	return next;
}
int KMP_Search(const char* MainStr, const char* SubStr, int start)
{
	//1.申请两个变量i和j
	//2.让变量i指向主串的开始字符位置，让变量j指向子串的第一个字符位置 获取next数组
	int i = start;
	int j = 0;
	int* next = Get_Next(SubStr);
	//3.进入while，循环条件是i和j都还合法
	while (i < (int)strlen(MainStr) && j < (int)strlen(SubStr))
	{
		//4.进入后比较i和j指向的字符
		//5.如果i和j指向的字符相同 则让i和j同步向后走一步
		if (j == -1)
		{
			i++;
			j++;
		}
		if (MainStr[i] == SubStr[j])
		{
			i++;
			j++;
		}
		//6.如果i和j指向的字符不同 则让j回退到合适的位置 i可以不用回退
		else
		{
			j = next[j];//j回退到next[j]
		}
	}
	//7.当while循环结束 我们去判断j是否越界 如果j越界说明查找成功 返回i-j 如果失败返回-1
	if (j < (int)strlen(SubStr))return -1;
	return i - j;
}
int main()
{
	const char* MainStr = "ABABCABCDABCDE";
	const char* SubStr = "ABCD";
	int index = KMP_Search(MainStr, SubStr, 0);
	if (index == 1)printf("匹配失败\n");
	else printf("匹配成功 在%d位置查找成功\n", index);
	return 0;
}