C实现KMA算法的小细节

C实现KMA算法的小细节算法核心思想 利用已经部分配对的有效信息 让主串 i 指针不回溯 通过每次确定子串 j 指针的回溯位置 使得子串 模式串 重新匹配时尽量移动到**位置 以减少不必要的回溯 int GetNext char Str int Next int malloc sizeof int

大家好,我是讯享网,很高兴认识大家。

算法核心思想:

利用已经部分配对的有效信息,让主串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:


讯享网

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

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

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

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

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

小讯
上一篇 2025-03-04 14:00
下一篇 2025-01-17 21:35

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/130950.html