C实现KMA算法的小细节
算法核心思想:
利用已经部分配对的有效信息,让主串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原理详解
相关推荐
hugebawu 2020-10-12
风吹夏天 2020-07-18
pengkingli 2020-06-25
ustbfym 2020-06-17
wonner 2020-06-04
SystemArchitect 2020-06-02
dbhllnr 2020-05-15
wonner 2020-04-25
seekerhit 2020-04-20
yedaoxiaodi 2020-04-19
sunjunior 2020-03-08
faiculty 2020-03-03
dushine00 2020-02-18
nurvnurv 2020-02-02
troysps 2020-01-08
rein0 2020-01-01
yishujixiaoxiao 2019-12-30
baike 2019-12-03