珠海网站建设开发,优化大师平台,长兴网站建设公司,php网站开发技术描述个人主页#xff1a;【#x1f60a;个人主页】 系列专栏#xff1a;【❤️我欲修仙】 学习名言#xff1a;莫等闲、白了少年头#xff0c;空悲切。——岳飞 系列文章目录
第一章 ❤️ 学习前的必知知识 第二章 ❤️ 二分查找 文章目录系列文章目录前言#x1f697;… 个人主页【个人主页】 系列专栏【❤️我欲修仙】 学习名言莫等闲、白了少年头空悲切。——岳飞 系列文章目录
第一章 ❤️ 学习前的必知知识 第二章 ❤️ 二分查找 文章目录系列文章目录前言BF算法KMP算法介绍:算法主体next[]数组总结前言
进入修仙界你会遇见许多新奇事务认识新的好友还有许多奇遇那么废话少说让我们进入到今天的冒险吧! BF算法 BF算法即暴力(Brute Force)算法是普通的模式匹配算法BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配若相等则继续比较S的第二个字符和 T的第二个字符若不相等则比较S的第二个字符和T的第一个字符依次比较下去直到得出最后的匹配结果。BF算法是一种蛮力算法。 int BF( char* b, char* a)
{int i 0, j 0; int ret i;//用来控制主串用来控制子串ret用来记录若有完整的匹配的字符串时该字符串的起始位置//当主串和子串都不为\0时进入循环进行比对while (*(b i) *(a j)){//如果对应元素相同则都指向下一位if (*(b i) *(a j)){i;j;}//不同则让i回到主串的上一次比较过的元素的第一个元素的后一元素j赋为0子串重新比对//ret则等于新的起始位置else{i i - j 1;j 0;ret i;}}//若主串对应的元素为则代表遍历完成主串没有与子串相匹配的字符串if (*b \0){return -1;}//if如果不执行下面这个return便会执行。返回下标。return ret;
}显然这种暴力的算法并不高效于是KMP算法就诞生了。
KMP算法
介绍: KMP算法是一种改进的字符串匹配算法由D.E.KnuthJ.H.Morris和V.R.Pratt提出的因此人们称它为克努特—莫里斯—普拉特操作简称KMP算法。KMP算法的核心是利用匹配失败后的信息尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(mn) KMP算法主要分为两部分1.算法主体 2.获取next[]数组
算法主体
让我们忽略next[]的由来只是关注算法主体算法可以写成
int KMP_S(char *a,char *b,int Len_p,int Len_s)
{int i 0, j 0;int* next build_next(b,Len_s);//获取next[]数组while (i Len_p){if (*(a i) *(b j)){i;j;}//如果两个数相同这两个数组都向下移动 else if (j 0)j *(nextj-1);//非第一个字符从跳过next数重新匹配elsei;//第一个字符匹配时就失配if (j Len_s)return i - j;//返回下标值}
}next[]数组
next[]数值代表的是在匹配失败的时候字串中可以跳过匹配的字符个数通过观察我们不难发现我们跳过的字符与后面的字符完全相同即前缀和后缀相同所以我们可以认为next[]数组的本质就是寻找子串中“相同前后缀的长度并且一定是最长的前后缀”不包括其本身 我们可以使用递归的方式去求解next[]数组
int* build_next(int* b, int Len_s)
{int i, j 0;int next[MAX] { 0 };for (i 1;i Len_s;i){while (j 0 *(b i) ! *(b j)){j next[i - 1];}if (*(b i) *(b j)){next[i] j;}}return next;
}总结
KMP算法比较难以理解我发现网上大部分讲解KMP算法的文章都比较难懂事实上在这方面我认为还是通过动画视频的方式可以更加直观的认识到KMP算法的运算方式。 这里我推荐最浅显易懂的 KMP 算法讲解
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestring.h
#define MAX 100
int next[MAX] { 0 };
/*int* build_next(int* b, int Len_s)
{int i, j 0;int next[MAX] { 0 };for (i 1;i Len_s;i){while (j 0 *(b i) ! *(b j)){j next[i - 1];}if (*(b i) *(b j)){next[i] j;}}return next;
}*/
int* build_next(char* b, int Len_s)
{int next[MAX] { 0 };int len 0, i 0;while (i Len_s){if (*(b len) *(b i)){len;next[i] len;i;}else if (len 0){next[i] 0;i;}elselen next[len - 1];}return next;}//求解next*/
int KMP_S(char *a,char *b,int Len_p,int Len_s)
{int i 0, j 0;int* next build_next(b,Len_s);while (i Len_p){if (*(a i) *(b j)){i;j;}//匹配成功向下移动 else if (j 0)j *(nextj-1);//非第一个字符从跳过next数重新匹配elsei;//第一个字符匹配时就失配if (j Len_s)for (;j i;j){printf(%c, *(a j));return i - j;}}
}
int main()
{char Pst[MAX] { 0 };char Sst[MAX] { 0 };int Len_p 0;int Len_s 0;fgets(Pst, MAX, stdin);getchar();fgets(Sst, MAX, stdin);Len_p strlen(Pst)-1;Len_s strlen(Sst);printf(%d %d\n, Len_p, Len_s);KMP_S(Pst, Sst,Len_p,Len_s);return 0;
}部分文字与图片来源于网络侵权请联系删除
