院士 顶顺表哥，话说表哥好久没冒泡了，能说下需要那几个参数不？[em_13]

void get_next(unsigned char* t , int tl, int* next) //获取回溯的表
{

	int len = tl;
	int i = 0;
	int j = -1;  //尾缀
	next[0] = -1; //前缀
	while (i < len)
	{
		if (j == -1 || t[i] == t[j])
		{
			j++;
			i++;

			//与普通KMP差异的地方
			if (t[i] != t[j])
			{
				next[i] = j;
			}
			else
			{
				next[i] = next[j];
				//这个主要是考虑匹配失败的时候，如果匹配失败了，必然往回回溯，但是如果回溯的下一个
				//地方还是这个元素，必然没有意义，还要往前回溯，那就把前一个元素的回溯值直接交给后面就可以了

				//比如  S = abacababc
				//		T = abab
				//匹配第四个元素不同，必然往前回溯，变成
				//      S = abacababc
				//		  T = abab
				//对着的还是b，不可能匹配成功的。
				//所以，如果有匹配的子串，而且其下一个元素也相同，那就意味着，如果下一个元素匹配失败的时候
				//往前回溯，对应元素还是这个值。
			}
			//差异结束

		}
		else
		{
			j = next[j]; 
		}
	}
}

int Index_KMP(unsigned char* S , int SLength, unsigned char* T , int TLength)
{
	int next[260]={0};
	get_next(T,TLength, next);//获取模式串用于标识回溯位置的表
	int i = 0;
	int j = 0;
	int Slen = SLength;//主串
	int Tlen = TLength; //模式串

	while (i < Slen && j < Tlen)
	{
		if (j == -1 || S[i] == T[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j == Tlen)//匹配成功
	{
		return i - j;
	}
	else
	{
		return -1;
	}

}

也备用一个搜索代码. 方便以后查找.

Mxixihaha void get_next(unsigned char* t , int tl,&n ...

听群里的表哥说这种回帖,就是要竞速的意思...

上2张,我自己测试的搜索速度对比,仁兄可自行试试,再接再厉

如果只是纯碎的想测试对kmp的优化,

可以改下搜索过程中的哈希表的坏字符的使用

改成如下,就是纯碎的kmp优化模式

优化的思想,基本在楼上pyg那边相关帖子说过了,不重复了