首页 > 代码库 > 【基本算法】 KMP文本串模式串的字符串匹配算法
【基本算法】 KMP文本串模式串的字符串匹配算法
看了两个晚上的KMP,加上基本的“暴力匹配”
今晚看懂next[j]递归求解时,突然觉得算法真的好美妙,虽然觉悟的晚但晚胜过没有是吧!
我的博客都是应试性的学习笔记,不具备指导性,还是大神们写的好,例如July和matrix67的博客(今天还知道了matrix67的传奇)
[置顶] 从头到尾彻底理解KMP(2014年8月22日版)
[置顶] 从头到尾彻底理解KMP(2014年8月22日版)
实习辞职了,可以全心全意看书找工作了,自由真是好!!为了我们俩以后在一起!!
什么时候努力都不晚,尽管我的路走的有些曲折,这鸡汤给自己灌得好哇!
今天菜鸟是为了明天的自己不菜鸟,扯多了……
KMP面对的问题:长串(文本串)是S串,短串(模式串)是P串,判断P串是否是S的一个子串,如果是找到P在S中的起始位置
S串 索引i
P串 索引j
KMP的思想:(假设这里已了解“暴力匹配”算法)
①当p0,p1……pj-1与si-j,si-j+1,……si-1匹配,但pj!=si时,j不必回到0开始匹配
②而是分析P串本身的性质,让“j少回溯一些”,这就和next[j]数组的求值有关
③……(果然看懂和写出来不是一个段位的,图书馆要关门了,先写到这)
附上自己实现代码
#include <iostream>#include <string>using namespace std;//KMP算法,分析短串P中本身的性质,寻找“前缀==后缀的最长串”,从而令索引j少往回走一些void getNext(char *p, int next[]){ int k=-1; int j=0; next[0]=-1; int pLen=strlen(p); while(j<pLen-1){ if (k==-1||p[k]==p[j]){ j++; k++; next[j]=k; }else k=next[k];//这里有点晦涩啊,但正是递归的精华所在 }}int KmpSearch(char *s, char *p){ int i=0,j=0; int sLen=strlen(s); int pLen=strlen(p); int *next=new int[pLen]; getNext(p,next); while (i<sLen && j<pLen){ if (j==-1 || s[i]==p[j])//这里j=-1还不理解 { i++; j++; }else j=next[j]; } delete next; if(j==pLen) return i-j; else return -1;}int main(){ char *s1="bbc abcdab abcdabcdabde"; char *s2="abcdabd"; cout<< KmpSearch(s1, s2) <<endl; return 0;}
【基本算法】 KMP文本串模式串的字符串匹配算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。