首页 > 代码库 > 【基本算法】 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文本串模式串的字符串匹配算法