dede个人网站,建设高校实验室教学网站的作用,北京到广州飞机,十大免费推广平台介绍
什么是KMP算法#xff1a;
KMP算法主要运用串的模式匹配中#xff08;简单来说就是在s串中找到一个与t串相等的子串#xff0c;称为模式匹配#xff09;例如s为abcdef#xff0c;t为bcd#xff0c;那么就是在s中找到bcd#xff0c;并返回其在s中的首下标#xf…介绍
什么是KMP算法
KMP算法主要运用串的模式匹配中简单来说就是在s串中找到一个与t串相等的子串称为模式匹配例如s为abcdeft为bcd那么就是在s中找到bcd并返回其在s中的首下标该算法和BF算法相比有比较大的改进主要是消除了主串指针的回溯从而使算法的效率有了某种程度的提高。了解这些就够了其他都是废话
有些读者可能不了解什么使BF算法下面我简单讲解一下了解的读者可跳过
BF算法
可以看到BF算法其实就是类似遍历一定可行但是时间复杂度是Om*nm为s的字符个数n为t的字符个数效率太低了KMP算法就是对它的改进
思维图如下 代码如下解释都在代码里了
#define _CRT_SECURE_NO_WARNINGS 1
//BF算法
#include stdio.h
#include string.h
typedef struct
{char data[1000];int length;
}SqString;
int index(SqString s, SqString t)
{int i 0, j 0;while (i s.length j t.length){if (s.data[i] t.data[j]) //继续匹配下一个字符{i; //主串和子串依次匹配下一个字符j;}else //主串、子串指针回溯重新开始下一次匹配{i i - j 1; //主串从下一个位置开始匹配j 0; //子串从头开始匹配}}if (j t.length)return(i - t.length); //返回匹配的第一个字符的下标elsereturn(-1); //模式匹配不成功
}
int main()
{SqString s, t;strcpy(s.data, ababcabcacbab);strcpy(t.data, abcac);s.length 13;t.length 5;printf(位置:%d\n, index(s, t));return 1;
}接着就是我们的重头戏KMP算法了解了BF算法我们发现每次比较完若不匹配指向s的指针要进行回溯那有没有办法让指向s的指针不回溯一直向前这样是不是效率就会高很多。
KMP算法
分为两步
第一步求next数组是关于t串的数组
我先给出代码如果理解这个代码直接看第二步
一开始看不懂很正常因为非常抽象花掉一个早上理解这个代码都算正常的
求解next数组代码如下别小看这个和递归一样小小代码大大能量
void GetNext(SqString t, int next[])
{int j, k;j 0, k -1;next[0] -1;while (j t.length - 1){if (k -1 || t.data[j] t.data[k]){k; j;next[j] k;}else k next[k];}
}
为什么要求next数组呢这是因为KMP算法比较过程其实是让t串进行移动理解这个非常重要next数组存储当前可以移动多少个字符。
概念对于t[j]的每个字符存在一个整数k使得模式串t中开头的k个字符t[0]t[1]...t[k-1]依次与t[j]的前面k个字符t[j-k]t[j-k1]....t[j-1]这里t[j-k]最多从t[1]开始。如果这样的k有多个取最大的一个模式串t中每个位置j的字符都有这种信息采用next[j]数组表示,及next[j] MAX(k).
概念如上不理解很正常下面我会用图画来帮助大家理解包括我从不懂到理解的一些经验 首先总体next我先给出下面会逐一分析
总体next不懂没关系看下面的 规定next[0]为-1这是规定不必深究B前面只有A故next[1]为0
找k的规则大一点的看的比较清楚我就先讲为什么下标7的B下面的k为什么为3找的时候一个必须从0开始另一个的结尾必须是下标7的前一个7下标对应的k是反应前6个不包括本身。
其中特别注意从0开始的哪个不能超过j从j前面为结尾的不能往前到0这其实就是前后缀的概念防止太乱我给了两张图片 第一步 next【0】规定为-1next【1】前面只有A显然为0自己本身不算相等next【2】要记得我上面讲的前后缀
第二步 后面类似就麻烦读者自行完成。
将上面的图解归纳起来就得到了一个求解next数组的公式 下面那个代码再理解理解上是手算下面是代码实现要理解一下特别注意k每次最多增加1knext【k】是k回退因为不相等读者可以自己画图帮助理解一下
void GetNext(SqString t, int next[])
{int j, k;j 0, k -1;next[0] -1;while (j t.length - 1){if (k -1 || t.data[j] t.data[k]){k; j;next[j] k;}else k next[k];}
}
接着就是
第二步KMP算法的模式匹配过程
一样我先给代码
int KMPIndex(SqString s, SqString t)
{int i 0, j 0;int next[20];GetNext(t, next);while (i s.length j t.length){if (j -1 || s.data[i] t.data[j]){j; i;}else j next[j];}if (j t.length) return (i-t.length);else return -1;
}
有了next数组的帮助我们就可以知道当模式串t与s串不同时t串要向右移动多少个字符
整个过程图解如下 相信细心的同学发现KMP算法其实是移动t串s串是一直向前的。
总代码如下
c语言
#define _CRT_SECURE_NO_WARNINGS 1
//串的模式匹配
//kmp求解
#include stdio.h
#include string.h
typedef struct
{char data[1000];int length;
}SqString;
void GetNext(SqString t, int next[])
{int j, k;j 0, k -1;next[0] -1;while (j t.length - 1){if (k -1 || t.data[j] t.data[k]){k; j;next[j] k;}else k next[k];}
}
int KMPIndex(SqString s, SqString t)
{int i 0, j 0;int next[20];GetNext(t, next);while (i s.length j t.length){if (j -1 || s.data[i] t.data[j]){j; i;}else j next[j];}if (j t.length) return (i - t.length);else return -1;
}
int main()
{SqString s1, s2;strcpy(s1.data, abcdefg);strcpy(s2.data, de);s1.length 7;s2.length 2;int t KMPIndex(s1, s2);printf(%d, t);return 0;
}
c版的如下
//KMP算法
#include sqstring.cpp
void GetNext(SqString t,int next[]) //由模式串t求出next值
{int j,k;j0;k-1;next[0]-1;while (jt.length-1) { if (k-1 || t.data[j]t.data[k]) //k为-1或比较的字符相等时{printf((1)j%d,k%d,两个指向字符相同,j,k);printf(,执行j,k - );j;k;next[j]k;printf((1) j%d,k%d,next[%d]%d\n,j,k,j,k);}else{printf((2)j%d,knext[%d],j,k);knext[k];printf(%d\n,k);}}
}
int KMPIndex(SqString s,SqString t) //KMP算法
{int next[MaxSize],i0,j0;GetNext(t,next);while (is.length jt.length) {if (j-1 || s.data[i]t.data[j]) {i;j; //i,j各增1}else jnext[j]; //i不变,j后退}if (jt.length)return(i-t.length); //返回匹配模式串的首字符下标else return(-1); //返回不匹配标志
}
/*
int main()
{SqString s,t;StrAssign(s,ababcabcacbab);StrAssign(t,abcac);printf(s:);DispStr(s);printf(t:);DispStr(t);printf(位置:%d\n,KMPIndex(s,t));return 1;
}
*/int main()
{SqString s,t;StrAssign(t,aaba);//StrAssign(t,aaaac);printf(t:);DispStr(t);int next[100];GetNext(t,next);return 1;
}
力扣例题1408
帮助大家巩固知识点。
结语
其实写博客不仅仅是为了教大家同时这也有利于我巩固自己的知识点和一个学习的总结对文章有任何问题的还请指出接受大家的批评让我改进如果大家有所收获的话还请不要吝啬你们的点赞和收藏这可以激励我写出更加优秀的文章。
如果大家还是不太理解的话可以评论区提问我都会解答或者可以看b站的【最浅显易懂的 KMP 算法讲解-哔哩哔哩】 https://b23.tv/cvI5JKf
