KMP算法原理与实现(精简)
发布时间:2020-12-16 07:48:15 所属栏目:百科 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 思想:使源字符串中的下标不回溯,利用模式字符串自身的相关性,减少模式字符串中下标回溯的距离。从而减少比较的次数。 #include stdio.h#include st
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考
思想:使源字符串中的下标不回溯,利用模式字符串自身的相关性,减少模式字符串中下标回溯的距离。从而减少比较的次数。
#include <stdio.h> #include <string.h> #include <malloc.h> void get_next(int next[],char source[],int n);//获取部分匹配字符数组 int Index_KMP(char* s_string,char* t_string,int pos);//返回源字符串s_string中pos开始 与t_string匹配的第一个字符串首字母下标,无匹配返回0 int main() { char *source_str = "BBC ABCDAB ABCDABCDABDE"; char *t_str = "ABCDAB";//模式串 printf("%dn",Index_KMP(source_str,t_str,8)); return 0; } void get_next(int next[],int n) { int i = 0; next[0] = 0; for(i = 1; i < n; i++) { if(source[i] == source[next[i-1]]) next[i] = next[i-1] + 1; else next[i] = 0; } } int Index_KMP(char* s_string,int pos) { int i = pos;//指向 s_string的起始下标 int j = 0;//指向 t_string的起始下标 int t_len = strlen(t_string); int s_len = strlen(s_string); int* t_next = (int*)malloc(sizeof(int)*t_len); int m; get_next(t_next,t_string,t_len);//获取t_string的部分匹配字符数组 for(m = 0; m < t_len; m++) printf("%d ",t_next[m]); printf("n"); while( (i<s_len)&&(j<t_len) ) { if(s_string[i] == t_string[j]) { i++; j++; } else { if(j == 0) { i++; //源字符串下表前移动 } else { m = j - t_next[j-1];//需回溯的位数 j = j - m;//设置下一次的起始坐标 } } } free(t_next); if(j==t_len) return i-t_len; else return 0; } 来自:http://blog.csdn.net/youxin2012/article/details/17083261 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |