学习Kmp算法

KMP算法是用于在文本串中判断是否存在子串（或称为模式串），并返回模式串在文本串中出现的位置的字符串算法。例如，文本串为text="caniwaitforyourheart"，模式串为pattern="wait"。我们可以很直观的看到文本串中是包含模式串的，且所在文本串的索引值为4。

暴力枚举法

算法思想

枚举文本串的起始位置i，然后从该位开始逐位与模式串进行对比

若每一位都相同，则匹配成功

若某一位出现不同，则起始位置继续变为i+1，而模式串索引则从头开始匹配

这种暴力的枚举法当文本串text很长时效率会变得很低，时间复杂度为O(n*m)，n和m为text和pattern的长度

Code

//暴力算法
//返回模式串在文本串中出现的位置
//不存在则返回-1
int count(char s[], char t[])
{	
	int i, j;
	//枚举文本串
	for (i = 0, j = 0;s[i] != '\0';i++) {
		if (s[i] == t[j]) {
			int _i = i, _j = j;
			while (s[_i] == t[_j]&& s[_i] != '\0'&& t[_j] != '\0') {
				_i++;
				_j++;
			}

			if (t[_j] == '\0')
				return i;
		}
		else
			j = 0;
	}
	
	return -1;
}

KMP登场

next[]数组

关于获取next[]数组最重要的就是理解i节点的回退。需要关注的是若i、j索引所代表的字符若一直不相同，i节点的回退的重点在哪。我是这么理解的，因为next[]数组的0位置默认是0，不会对其有什么操作，且又是数组的起始位置，当i一直减少到0时则视为重点，跳出while循环，这一点会在代码中有所体现；同时，当i、j索引所代表的字符相同的时候，i节点后移，刚好满足记录相同前缀的下一个节点所引。总之闲话不多说，上代码。

//构造next数组
void gen_next(char c[],int next[]) {
	int i=0, j;//i在前，j在后
	next[0] = 0;
	for (j = 1;c[j] != '\0';j++) {
		//当i=0初始位置时，且i、j索引位置的字符都不相等，则毫无疑问next[j]=0
		//这也是一个i索引回溯的while循环出口
		while (i!=0&&c[i] != c[j]) 
			i = next[i - 1];
			
		//当俩字符比较相同，i索引相加
		if (c[i] == c[j]) 
			i++;
		
		next[j] = i;
	}
}

kmp算法

元素相同指针同时后移
元素不同，则令j=next[j-1]，找到相同前缀的用于比较的下个next索引，并与文本串的i索引位置继续比较；若仍不同则重复此操作。

//代码与构造next数组相似
//求解next数组的过程其实就是模式串pattern进行自我匹配的过程
bool kmp(char str1[],char str2[]) {

	int* next = new int[strlen(str2)];
	gen_next(str2,next);
	int i = 0, j;
	for (j = 0;str1[j] != '\0';j++) {
		while (i!=0&& str1[j]!=str2[i]) 
			i = next[i - 1];
		
		if (str1[j] == str2[i])
			i++;

		if (str2[i] == '\0')
			return true;
	}
	return false;
}

疑问

可能有人会问，既然for循环中每个j都有一个while循环，这样i回退的次数可能不可预计，为什么KMP算法的复杂度时O（n+m）呢？

首先整个for循环中j是不断加1的，所以在整个过程中j的变化次数是O（n）级别，这个应该没有疑问。接下来考虑i的变化，我们注意到i只会在一行中增加，并且每次只加1，这样在整个过程中i最多只会增加n次；而其他地方的i都是不断减少的由于i最小不会小于0，因此在整个过程中i最多只能减少n次，因此i在整个过程中的变化过程是O（N）级别的。