算法核心思想:
利用已经部分配对的有效信息,让主串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原理详解

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