[数据结构与算法]2021-09-21

串KMP改进算法的c语言实现

书上还有好多博客上给出的示例代码都是从下标1开始的，那样虽然容易理解原理，但不是c语言的风格，所以自己调试了一个从下标0开始的实现代码。

//得到部分匹配表
void getNextval(char *pTstring, int ucTlen, int *pNext)
{
	int i,k;
	i = 0;
	k = -1;
	*pNext = -1;
	while(i < ucTlen)
	{
		if(k == -1 || *(pTstring+i) == *(pTstring+k))
		{
			++i;
			++k;
			if(*(pTstring+i) != *(pTstring+k))
			{
				*(pNext+i) = k;
			}
			else
			{
				*(pNext+i) = *(pNext+k);
			}
		}
		else
		{
			k = *(pNext+k);
		}
	}
	return;
}
//查找函数
int findIndex_kmp(char *pS, char sLen, char *pT, char tLen, int pos)
{
	int i = pos-1;
	int j= -1;
	int next[MAX_STRING_LEN];
	memset(next, 0, sizeof(next));
	getNextval(pT, tLen, &next[0]);
	while(i < sLen && j < tLen)
	{
		if(j == -1 || *(pS+i) == *(pT+j))
		{
			++i;
			++j;
		}
		else
		{
			j = next[j];
		}
	}
	if(j >= tLen)
	{
		return i-tLen;
	}
	else
	{
		return -1;
	}
}