字符串的匹配 BF算法 KMP算法

  【最浅显易懂的 KMP 算法讲解-哔哩哔哩】 https://b23.tv/G6EapaA

 【KMP算法之求next数组代码讲解-哔哩哔哩】 https://b23.tv/v9pCcYQ

 
// BF暴力方法寻找字符串
int Index_BF(SString S, SString T)
{
	int i = 1;//为了方便从下标为1开始存储
	int j = 1;
	while (i < S.length && j <= T.length)//这两个条件 分别对应了成功与失败两种
	{
		if (S.ch[i] == T.ch[j]) { i++; j++; }//符合就继续往下走
		else { i = i - j + 1 + 1; j = 1; }//不匹配就回去
 
 
	}
	if (j > T.length) return i - T.length;//这时候匹配成功了
	else return 0;//这时候匹配失败了 里面没有
}//时间效率是O（n*m）
 
 

 BF（暴力算法）

  为了后面的方便所以数组都下标都从1开始存储

while 里面的两条也分别对应着成功匹配和没有找到两种情况

如果那么子串和主串都往下走

如果不相同了i返回了刚才的前一位 

当j=4时候 j其实就走了三步（j的数量少，便于记录走了多少步 这时候j虽然为4但是仅仅走了三步） 所以说i要回到原来的那个数字后一位 就是 i-（j-1）+1

而j再回到第一步j=0； 

直到退出循环为止

---

//KMP算法匹配字符串
//优点：首先主串指针S不用回溯，时间效率可以提升到（n+m）
//先获得next数组
void GetNext(SString T, int next[])
{
	next[0] = 0;
	int i = 1, j = 0;
	while (i <= T.length)
	{
		if (j == 0 || T.ch[i] == T.ch[j]) { next[++i] = ++j; }//这里next[i+1]的值只能是由next[i]单递增1 因为他只移动了一位而已
		else j = next[j];//这里有递归的思想
	}
}
 
int Index_KMP(SString S, SString T, int pos)
{
	int i = pos;
	int j = 1;
	int next[10000];
	GetNext(T, next);
	while (i < S.length && j < T.length)
	{
		if (j == 0 || S.ch[i] == T.ch[j]) { i++; j++; }
		else j = next[j];//这里就是和上面最根本的区别：i不回溯了而只改变j
	}
 
}

KMP算法

KMP引出了 next数组 前缀 后缀 递归

BF算法每一次匹配不上 i 就会返回原来的下一位，j 回到第一位  

比如说 aaaaaab 中找 ab  根本没必要一个一个往后直接到最后一个a就行了

首先next数组是只与子串有关的

每次运行这一步才会成功给next数组赋一个值

 比如这个例子如果16号的值和8号的值相同那么就是4

如果不同就再往回到4 看16 和4的值是不是相同 直到找到相同的 如果到了j=0则就是前面没有前缀后缀相同的 也满足条件了 也进行赋值了

也成功完成了一次赋值

以上是next的赋值思想

这里的主算法跟BF的差不多

但是 i 不回溯，就是i一直往前，j一直根据next徘徊 j是一直变的