开发者社区> marsggbo> 正文

KMP算法C语言实现。弄了好久才搞好。。。

简介: 我的这个算法中数组的第一位没有像教材中那样用来存数组的大小,所以会有些许的不同。 // KMP算法 #include #include #include void get_next(char *T,int next[]) //修正前的next数组 { int i =...
+关注继续查看
我的这个算法中数组的第一位没有像教材中那样用来存数组的大小,所以会有些许的不同。
// KMP算法
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void get_next(char *T,int next[])	//修正前的next数组 
{
int i = 1,j = 0;
next[0] = -1;
next[1] = 0;
int m = strlen(T);
while(i<strlen(T)-1)
{
if(j == -1||T[j]==T[i])
{
++i;
++j;
next[i] = j;
}
else j = next[j];
}
} 

void get_nextval(char *T,int nextval[])	//修正后的nextval数组
{
int i = 1,j = 0;
nextval[0] = -1;
nextval[1] = 0;
int m = strlen(T);
while(i<strlen(T)-1)
{
if(j == -1||T[j]==T[i])
{
++i;
++j;
if(T[i]!=T[j]) nextval[i] = j;
else nextval[i] = nextval[j];
}
else j = nextval[j];
}
} 

int Index_kmp(char *S,char *T,int pos,int next[])	//逐项比较 
{
int j = 0,i = pos,lens=strlen(S),lent=strlen(T);
get_next(T,next);
while(i<lens&&j<lent)
{
if(S[i]==T[j]||j==-1)
{
i++;j++;
}
else j = next[j];
}
if(j>=lent) return i-lent;
else return -1;
}

int main()
{
char *S="adbadabbaabadabbadada",*T="adabbadada";
int m;
int *next = (int *)malloc((strlen(T)+1)*sizeof(int));	//修正前的next数组
int *nextval = (int *)malloc((strlen(T)+1)*sizeof(int));	//修正后的nextval数组

get_next(T,next);
printf("修正前next数组为:");
for(m = 0;m<strlen(T);m++)
{
printf("%d ",next[m]+1);
}

get_nextval(T,nextval);
printf("\n修正后的nextval数组为:");
for(m=0;m<strlen(T);m++)
{
printf("%d ",nextval[m]+1);
}


int t = Index_kmp(S,T,0,nextval);
if(t==-1) printf("\n无匹配项!\n");
else
{
printf("\n在第%d项开始匹配成功\n",t+1);
}
return 0;
}

  

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
将数组a中数据元素实现就地逆置的算法
给出将整型数组a中数据元素实现就地逆置的算法。所谓就地逆置,就是利用数组a原有空间来存放数组a中逆序排放后的各个数据元素。
177 0
【前端算法】JS实现数字千分位格式化
JS实现数字千分位格式化的几种思路,以及它们之间的性能比较
100 0
【前端算法】用JS实现快速排序
理解数组方法里面运用到的算法,splice 和 slice的区别
46 0
【前端算法】javaScript实现二分查找
如何使用JS实现一个合格的二分查找
79 0
【前端算法】链表和数组实现队列的区别
比较链表和数组实现队列的性能
78 0
【前端算法】两个栈实现一个队列
介绍栈和队列的区别,以及如何使用栈实现一个队列
48 0
一行代码解决LeetCode实现 strStr()使用JavaScript解题|前端学算法
一行代码解决LeetCode实现 strStr()使用JavaScript解题|前端学算法
60 0
Kalman算法C++实现代码(编译运行通过)
Kalman算法C++实现代码(编译运行通过)
79 0
一则有趣的算法题:两个栈实现一个队列
一则有趣的算法题:两个栈实现一个队列
40 0
C++ 实现KMP字符串匹配算法
C++ 实现KMP字符串匹配算法
45 0
+关注
marsggbo
AutoML
文章
问答
视频
文章排行榜
最热
最新
相关电子书
更多
阿里技术参考图册-算法篇
立即下载
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
相关实验场景
更多