C实现KMA算法的小细节

莫明天涯 2020-07-05

算法核心思想:

利用已经部分配对的有效信息,让主串i指针不回溯,通过每次确定子串j指针的回溯位置,使得子串(模式串)重新匹配时尽量移动到最佳位置,以减少不必要的回溯。

int* GetNext(char Str[])
{
   int* Next = (int*)malloc(sizeof(int) * strlen(Str));
   if (Next == NULL) return NULL;	
   int j = 0;
   int k = -1;
   Next[0] = -1;
   while (j < strlen(Str) - 1)
   {
   	if (k == -1 || Str[k] == Str[j])
   	{
   		j++;
   		k++;
   		if (Str[k] == Str[j])
   		{
   			Next[j] = Next[k];
   		}
   		else
   		{
   			Next[j] = k;
   		}
   	}
   	else
   	{
   		k = Next[k];
   	}
   }
   return Next;
}
int KMP(char T[], char P[])//T主串,P模式串
{
   int* Next = GetNext(P);
   if (Next == NULL) return -1;
   int i = 0;
   int j = 0;
   while (i < (int)strlen(T) && j < (int)strlen(P))
   {
   	if (j == -1 || T[i] == P[j])
   	{
   		i++;
   		j++;
   	}
   	else
   	{
   		j = Next[j];
   	}
   }
   printf("%d ", -1 < strlen(P));
   free(Next);
   return j == strlen(P) ? i - j : -1;
}

Details:

C实现KMA算法的小细节

strlen()函数的返回值是size_t类型,为无符号类型,而int是有符号类型。

当无符号类型的与有符号类型相比较的时候,有符号类型会自动转换成无符号类型。

C实现KMA算法的小细节

程序显示,10 > -1 是FALSE(0)的。这就是类型转换的问题。由补码可知,-1的补码转换成无符号类型是一个很大的数字。

C实现KMA算法的小细节

所以说,代码中的循环条件比较时一定要进行强制类型转换!!!

想深入了解KMP算法原理的小伙伴可以看看这个~
KMP原理详解

相关推荐