KMP匹配算法C语言版
2021/11/21 20:40:23
本文主要是介绍KMP匹配算法C语言版,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include<assert.h> #include<string.h> #include<stdlib.h> void GetNext(char* sub, int* next,int lenSub) { next[0] = -1; next[1] = 0; int i = 2;//当前i下标 int k = 0;//前一项的k while(i<lenSub) { if (k==-1 || sub[i - 1] == sub[k]) { next[i] = k + 1; i++; k++; } else { k = next[k]; } } } /* str 代表主串 sub 代表子串 pos 代表从主串的pos位置开始找 */ int KMP(char* str, char* sub, int pos) { assert(str != NULL && sub != NULL); int lenStr = strlen(str);//求主串的长度 int lenSub = strlen(sub);//求子串的长度 if (lenStr == 0 || lenSub == 0) { return -1; } if (pos<0 || pos>lenStr) { return -1; } int* next = (int*)malloc(sizeof(int) * lenSub); assert(next != NULL); GetNext(sub, next,lenSub); int i = pos;//遍历主串 int j = 0;//遍历子串 while (i < lenStr && j < lenSub) { if (j==-1 || str[i] == sub[j]) { i++; j++; } else { j = next[j]; } } if (j >= lenSub) { return i - j; } return -1; } int main() { printf("%d", KMP("ababcabcdabcde", "dabcde", 0));//5 从第五个位置开始匹配 return 0; } //nextval //1.回退到的位置和当前字符一样,就写回退那个位置的next值 //2.如果回退到的位置和当前字符不一样,就写当前字符原来的next值
这篇关于KMP匹配算法C语言版的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享