【数据结构】第四章 串

第四章 知识体系

4.1 串的定义和实现

4.2 串的模式匹配

4.2.1 BF简单模式匹配算法

4.2.2 KMP算法

4.2.3 KMP算法的优化

KMP算法的优化就是对next数组进行优化 并使用nextval作为新的模式串的回退数组，进而达到优化KMP算法，详细优化思想如下

代码如下：

//对next数组进行优化->生成nextval数组
void GetNextVal(char* str, int len, int* next, int* nextval){
	nextval[0] = 0;
	for(int j = 1; j <= len; ++j){
		if(str[j] == str[next[j]])
			nextval[j] = nextval[next[j]];
		else
			nextval[j] = next[j];
	}
}