快速认识KMP算法

阮一峰老师带你认识KMP算法

从头到尾彻底理解KMP

浅谈我对KMP中next数组的认识与理解

next数组是因为总是要找失配字符的上一位字符不方便而产生的

next数组的出现使得只用找失配字符对应的next值即为失配字符的上一位字符的最大长度值

  • 根据《最大长度表》，失配时，模式串向右移动的位数 = 已经匹配的字符数 - 失配字符的上一位字符的最大长度值
  • 而根据《next 数组》，失配时，模式串向右移动的位数 = 失配字符的位置 - 失配字符对应的next 值

有上述得匹配的字符数=失配字符的位置，失配字符的上一位字符的最大长度值=失配字符对应的next 值

next数组与最大长度表都是对模式串特征的一种映射，使得不需要像BF算法那样匹配多次，相同部分可以跳过

next数组的第一位为何是-1

由于第一位匹配就失配时，默认向右移动1位，即模式串向右移动的位数=1，此时失配字符的位置=0，代入（模式串向右移动的位数 = 失配字符的位置 - 失配字符对应的next 值）改式之中，即可解得next值为-1

next数组核心代码


//优化过后的next 数组求法
void GetNextval(char* p, int next[])
{
	int pLen = strlen(p);
	next[0] = -1;
	int k = -1;
	int j = 0;
	while (j < pLen - 1)
	{
		//p[k]表示前缀，p[j]表示后缀  
		if (k == -1 || p[j] == p[k])
		{
			++j;
			++k;
			//较之前next数组求法，改动在下面4行
			if (p[j] != p[k])
				next[j] = k;   //之前只有这一行
			else
				//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
				next[j] = next[k];
		}
		else
		{
			k = next[k];
		}
	}
}

KMP核心代码


int KmpSearch(char* s, char* p)
{
	int i = 0;
	int j = 0;
	int sLen = strlen(s);
	int pLen = strlen(p);
	while (i < sLen && j < pLen)
	{
		//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++    
		if (j == -1 || s[i] == p[j])
		{
			i++;
			j++;
		}
		else
		{
			//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]    
			//next[j]即为j所对应的next值      
			j = next[j];
		}
	}
	if (j == pLen)
		return i - j;
	else
		return -1;
}