Java教程

KMP模式匹配算法改进

本文主要是介绍KMP模式匹配算法改进，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

看这篇文章的前提是你已经了解过KMP模式匹配算法。针对KMP模式匹配算法中存在的无意义匹配进行优化。
在这里插入图片描述在这里插入图片描述
代码参考《大话数据结构》第五章第七节143页。

/*改进KMP模式算法*/
/*求模式串T的next函数修正值并存入数组nextval*/
void get_nextval(char* T, int* nextval)
{
	int i, j;
	i = 1;
	j = 0;
	nextval[1] = 0;
	while (i < T[0])/*此处T[0]表示串T的长度*/
	{
		if (j == 0 || T[i] == T[j])/*T[i]表示后缀的单个字符*/
								   /*T[j]表示前缀的单个字符*/
		{
			++i;
			++j;
			if (T[i] != T[j])/*判断，当前字符与前缀字符不同，*/
							 /*T[j]表示前缀的单个字符*/
				nextval[i] = j;
			else
				nextval[i] = nextval[j];/*字符的nextval值赋给nextval在i位置的值*/
		}
		else
			j = nextval[j];/*若字符不同，则j值回溯*/
	}

}
这篇关于KMP模式匹配算法改进的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航