精华内容
下载资源
问答
  • 数据结构 KMP算法代码

    千次阅读 2014-03-28 13:25:50
    //匹配字符串模式值  void getFail(char P[],int f[]) { int m=strlen(P); f[0]=0; f[1]=0; for(int i=1;i { int j=f[i]; while(j&&P[i]!=P[j])  j=f[j]; f[i+1] =P[i]==P[j] ?...//比较匹配算法 
    //匹配字符串模式值 
    void getFail(char P[],int f[])
    {
    int m=strlen(P);
    f[0]=0;
    f[1]=0;
    for(int i=1;i<m;i++)
    {
    int j=f[i];
    while(j&&P[i]!=P[j])
     j=f[j];
    f[i+1] =P[i]==P[j] ? j+1:0;
    }
    }




    //比较匹配算法 
    int find(char T[],char P[],int f[])
    {
    int n=strlen(T),m=strlen(P);
    getFail(P,f);
    int j=0,count=0;
    for(int i=0;i<n;i++)
    {
    while(j&&P[j]!=T[i]) 
     j=f[j];
    if(P[j]==T[i])
     j++;
    if(j==m) 
     //printf("%d\n",i-m+1);
     count++;
    }
    return count;
    }
    展开全文
  • 数据结构KMP算法

    2020-03-08 12:18:39
    数据结构KMP算法代码,并对KMP算法进行了改进优化,注释详细,易于理解,并附带举例说明。。。。。。
  • 数据结构KMP算法配图详解(超详细)

    千次阅读 多人点赞 2020-02-18 22:02:42
    KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法代码很优美简洁干练,但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂...

    KMP算法配图详解

    前言

    KMP算法是我们数据结构串中最难也是最重要的算法。难是因为KMP算法的代码很优美简洁干练,但里面包含着非常深的思维。真正理解代码的人可以说对KMP算法的了解已经相当深入了。而且这个算法的不少东西的确不容易讲懂,很多正规的书本把概念一摆出直接劝退无数人。这篇文章将尽量以最详细的方式配图介绍KMP算法及其改进。文章的开始我先对KMP算法的三位创始人Knuth,Morris,Pratt致敬,懂得这个算法的流程后你真的不得不佩服他们的聪明才智。

    KMP解决的问题类型

    KMP算法的作用是在一个已知字符串中查找子串的位置,也叫做串的模式匹配。比如主串s=“goodgoogle”,子串t=“google”。现在我们要找到子串t 在主串s 中的位置。大家肯定觉得这还不简单,不就在第五个嘛,一眼就看出来了。
    当然,在字符串非常少时,“肉眼观察法”不失为一个好方法。但如果要你在一千行文本里找一个单词,我想一般人都会数得崩溃吧。这就让我想起来考试的时候,如果一两道选择题不会。这时候,“肉眼观察法”可能效果不错,但是如果好几道大题不会呢?“肉眼观察法”就丝毫不起效了。所以打铁还需自身硬,我们把这种枯燥的事以一定的算法交给计算机处理。
    第一种我们容易想到的就是暴力求解法。
    这种方法也叫朴素的模式匹配

    简单来说就是:从主串s 和子串t 的第一个字符开始,将两字符串的字符一一比对,如果出现某个字符不匹配,主串回溯到第二个字符,子串回溯到第一个字符再进行一一比对。如果出现某个字符不匹配,主串回溯到第三个字符,子串回溯到第一个字符再进行一一比对…一直到子串字符全部匹配成功。

    下面我们通过图片展示这个过程:
    竖直线表示相等,闪电线表示不等
    第一个过程:子串“goo”部分与主串相等,'g’不等,结束比对,进行回溯。
    在这里插入图片描述
    第二个过程:开始时就不匹配,直接回溯
    在这里插入图片描述
    第三个过程:开始时即不匹配,直接回溯
    在这里插入图片描述
    第四个过程:开始时即不匹配,直接回溯
    在这里插入图片描述
    第五个过程:匹配成功
    在这里插入图片描述
    大家可能会想:这个方法也太慢了吧!求一个子串位置需要太多的步骤。而且很多步骤根本不必要进行。
    这个想法非常好!!很多伟大的思想都是在一步步完善更正已有方法中诞生的。这种算法在最好情况下时间复杂度为O(n)。即子串的n个字符正好等于主串的前n个字符,而最坏的情况下时间复杂度为O(m*n)。相比而言这种算法空间复杂度为O(1),即不消耗空间而消耗时间。

    下面就开始进入我们的正题:KMP算法是怎样优化这些步骤的。其实KMP的主要思想是:“空间换时间”。
    大家打起精神,认真看下面的内容
    首先,为什么朴素的模式匹配这么慢呢?
    你再回头看一遍就会发现,哦,原来是回溯的步骤太多了。所以我们应该尽量减少回溯的次数。
    怎样做呢?比如上面第一个图:当字符’d’与’g’不匹配,我们保持主串的指向不变,
    主串依然指向’d’,而把子串进行回溯,让’d’与子串中’g’之前的字符再进行比对。
    如果字符匹配,则主串和子串字符同时右移。
    至于子串回溯到哪个字符,这个问题我们先放一放。

    我先提出一个概念:一个字符串最长相等前缀和后缀。
    教科书常用的手段是:在此处摆出一堆数学公式让大家自行理解。
    在这里插入图片描述
    这也是为什么看计算机学科的书没有较好的数学基础会很痛苦。(当初我为什么不好好学数学T_T)
    大家先不要强行理解数学公式,且听我慢慢道来:
    我给大家个例子。
    字符串 abcdab
    前缀的集合:{a,ab,abc,abcd,abcda}
    后缀的集合:{b,ab,dab,cdab,bcdab}
    那么最长相等前后缀不就是ab嘛.

    做个小练习吧:
    字符串:abcabfabcab中最长相等前后缀是什么呢:
    对就是abcab
    好了我们现在会求一个字符串的前缀,后缀以及最长相等前后缀了。
    这个概念很重要。到这里如果都看懂了,可以鼓励一下自己,然后回想一遍,再往下看。
    之前留了一个问题,子串回溯到哪个字符,现在可以着手解决了。

    图解KMP

    现在我们先看一个图:第一个长条代表主串,第二个长条代表子串。红色部分代表两串中已匹配的部分,
    绿色和蓝色部分分别代表主串和子串中不匹配的字符。
    再具体一些:这个图代表主串"abcabeabcabcmn"和子串"abcabcmn"。
    在这里插入图片描述
    在这里插入图片描述
    现在发现了不匹配的地方,根据KMP的思想我们要将子串向后移动,现在解决要移动多少的问题。
    之前提到的最长相等前后缀的概念有用处了。因为红色部分也会有最长相等前后缀。如下图:
    在这里插入图片描述
    在这里插入图片描述
    灰色部分就是红色部分字符串的最长相等前后缀,我们子串移动的结果就是让子串的红色部分最长相等前缀和主串红色部分最长相等后缀对齐。
    在这里插入图片描述
    在这里插入图片描述
    这一步弄懂了,KMP算法的精髓就差不多掌握了。接下来的流程就是一个循环过程了。事实上,每一个字符前的字符串都有最长相等前后缀,而且最长相等前后缀的长度是我们移位的关键,所以我们单独用一个next数组存储子串的最长相等前后缀的长度。而且next数组的数值只与子串本身有关。
    所以next[i]=j,含义是:下标为i 的字符前的字符串最长相等前后缀的长度为j。
    我们可以算出,子串t= "abcabcmn"的next数组为next[0]=-1(前面没有字符串单独处理)
    next[1]=0;next[2]=0;next[3]=0;next[4]=1;next[5]=2;next[6]=3;next[7]=0;

    a b c a b c m n
    next[0] next[1] next[2] next[3] next[4] next[5] next[6] next[7]
    -1 0 0 0 1 2 3 0

    本例中的蓝色c处出现了不匹配(是s[5]!=t[5]),
    在这里插入图片描述
    我们把子串移动,也就是让s[5]与t[5]前面字符串的最长相等前缀后一个字符再比较,而该字符的位置就是t[?],很明显这里的?是2,就是不匹配的字符前的字符串 最长相等前后缀的长度。
    在这里插入图片描述
    也是不匹配的字符处的next数组next[5]应该保存的值,也是子串回溯后应该对应的字符的下标。 所以?=next[5]=2。接下来就是比对是s[5]和t[next[5]]的字符。这里也是最奇妙的地方,也是为什么KMP算法的代码可以那么简洁优雅的关键。
    我们可以总结一下,next数组作用有两个:
    一是之前提到的,

    next[i]的值表示下标为i的字符前的字符串最长相等前后缀的长度。

    二是:

    表示该处字符不匹配时应该回溯到的字符的下标

    next有这两个作用的源头是:之前提到的字符串的最长相等前后缀
    想一想是不是觉得这个算法好厉害,从而不得不由衷佩服KMP算法的创始人们。

    KMP算法的时间复杂度

    现在我们分析一下KMP算法的时间复杂度:
    KMP算法中多了一个求数组的过程,多消耗了一点点空间。我们设主串s长度为n,子串t的长度为m。求next数组时时间复杂度为O(m),因后面匹配中主串不回溯,比较次数可记为n,所以KMP算法的总时间复杂度为O(m+n),空间复杂度记为O(m)。相比于朴素的模式匹配时间复杂度O(m*n),KMP算法提速是非常大的,这一点点空间消耗换得极高的时间提速是非常有意义的,这种思想也是很重要的。
    下面还有更厉害的,我们一起来分析具体的代码。

    求next数组的代码

    下面我们一起来欣赏计算机如何求得next数组的

    typedef struct
    {	
    	char data[MaxSize];
    	int length;			//串长
    } SqString;
    //SqString 是串的数据结构
    //typedef重命名结构体变量,可以用SqString t定义一个结构体。
    void GetNext(SqString t,int next[])		//由模式串t求出next值
    {
    	int j,k;
    	j=0;k=-1;
    	next[0]=-1;//第一个字符前无字符串,给值-1
    	while (j<t.length-1) 
    	//因为next数组中j最大为t.length-1,而每一步next数组赋值都是在j++之后
    	//所以最后一次经过while循环时j为t.length-2
    	{	
    		if (k==-1 || t.data[j]==t.data[k]) 	//k为-1或比较的字符相等时
    		{	
    			j++;k++;
    			next[j]=k;
    			//对应字符匹配情况下,s与t指向同步后移
    			//通过字符串"aaaaab"求next数组过程想一下这一步的意义
    			//printf("(1) j=%d,k=%d,next[%d]=%d\n",j,k,j,k);
           	}
           	else
    		{
    			k=next[k];
    			**//我们现在知道next[k]的值代表的是下标为k的字符前面的字符串最长相等前后缀的长度
    			//也表示该处字符不匹配时应该回溯到的字符的下标
    			//这个值给k后又进行while循环判断,此时t.data[k]即指最长相等前缀后一个字符**
    			//为什么要回退此处进行比较,我们往下接着看。其实原理和上面介绍的KMP原理差不多
    			//printf("(2) k=%d\n",k);
    		}
    	}
    }
    

    解释next数组构造过程中的回溯问题

    大家来看下面的图:
    下面的长条代表子串,红色部分代表当前匹配上的最长相等前后缀,蓝色部分代表t.data[j]。
    在这里插入图片描述在这里插入图片描述

    KMP算法代码解释

    int KMPIndex(SqString s,SqString t)  //KMP算法
    {
    
    	int next[MaxSize],i=0,j=0;
    	GetNext(t,next);
    	while (i<s.length && j<t.length) 
    	{
    		if (j==-1 || s.data[i]==t.data[j]) 
    		{
    			i++;j++;  			//i,j各增1
    		}
    		else j=next[j]; 		//i不变,j后退,现在知道为什么这样让子串回退了吧
        }
        if (j>=t.length)
    		return(i-t.length);  	//返回匹配模式串的首字符下标
        else  
    		return(-1);        		//返回不匹配标志
    }
    

    KMP算法的改进

    为什么KMP算法这么强大了还需要改进呢?
    大家来看一个例子:
    主串s=“aaaaabaaaaac”
    子串t=“aaaaac”
    这个例子中当‘b’与‘c’不匹配时应该‘b’与’c’前一位的‘a’比,这显然是不匹配的。'c’前的’a’回溯后的字符依然是‘a’。
    我们知道没有必要再将‘b’与‘a’比对了,因为回溯后的字符和原字符是相同的,原字符不匹配,回溯后的字符自然不可能匹配。但是KMP算法中依然会将‘b’与回溯到的‘a’进行比对。这就是我们可以改进的地方了。我们改进后的next数组命名为:nextval数组。KMP算法的改进可以简述为: 如果a位字符与它next值指向的b位字符相等,则该a位的nextval就指向b位的nextval值,如果不等,则该a位的nextval值就是它自己a位的next值。 这应该是最浅显的解释了。如字符串"ababaaab"的next数组以及nextval数组分别为:

    下标 0 1 2 3 4 5 6 7
    子串 a b a b a a a b
    next -1 0 0 1 2 3 1 1
    nextval -1 0 -1 0 -1 3 1 0

    我们来分析下代码:

    void GetNextval(SqString t,int nextval[])  
    //由模式串t求出nextval值
    {
    	int j=0,k=-1;
    	nextval[0]=-1;
       	while (j<t.length) 
    	{
           	if (k==-1 || t.data[j]==t.data[k]) 
    		{	
    			j++;k++;
    			if (t.data[j]!=t.data[k]) 
    //这里的t.data[k]是t.data[j]处字符不匹配而会回溯到的字符
    //为什么?因为没有这处if判断的话,此处代码是next[j]=k;
    //next[j]不就是t.data[j]不匹配时应该回溯到的字符位置嘛
    				nextval[j]=k;
               	else  
    				nextval[j]=nextval[k];
    //这一个代码含义是不是呼之欲出了?
    //此时nextval[j]的值就是就是t.data[j]不匹配时应该回溯到的字符的nextval值
    //用较为粗鄙语言表诉:即字符不匹配时回溯两层后对应的字符下标
           	}
           	else  k=nextval[k];    	
    	}
    
    }
    
    int KMPIndex1(SqString s,SqString t)    
    //修正的KMP算法
    //只是next换成了nextval
    {
    	int nextval[MaxSize],i=0,j=0;
    	GetNextval(t,nextval);
    	while (i<s.length && j<t.length) 
    	{
    		if (j==-1 || s.data[i]==t.data[j]) 
    		{	
    			i++;j++;	
    		}
    		else j=nextval[j];
    	}
    	if (j>=t.length)  
    		return(i-t.length);
    	else
    		return(-1);
    }
    

    剩下的话

    在写这篇博客时,我想起了编译原理老师讲过的一些知识,其实KMP算法的步骤与自动机有不少相似之处,有兴趣的朋友不妨联系对比一下。

    展开全文
  • KMP算法中虽然计算了nextval的值,但我在此次并没有用到。 课程名称:数据结构 实验项目名称:串基本操作的实现 实验目的: 1.掌握串的模式匹配操作。 实验要求: ...3、 KMP算法代码; 4、 输

    KMP算法中虽然计算了nextval的值,但我在此次并没有用到。


    课程名称:数据结构

    实验项目名称:串基本操作的实现

    实验目的:

    1.掌握串的模式匹配操作。

    实验要求:

    1、    分别使用BF和KMP算法完成串的模式匹配。

    实验过程:

    1、    设计完成next值的计算函数;

    2、    设计完成修正next值的函数;

    3、    KMP算法代码;

    4、    输入子串(abbc)和主串(abbabbcad)

    5、    输出子串在主串中开始的位置。

    实验报告中给出next,修正next,KMP及主函数的代码。

    实验结果:

    输入: 子串:abbc; 主串:abbabbcad

    输出:4

    实验分析:

    1.普通next和修正next的区别;

    2.列举调试运行过程中出现的错误并分析原因。

    要求:

    (1) 程序要添加适当的注释,程序的书写要采用缩进格式

    (2) 程序要具在一定的健壮性,即当输入数据非法时,程序也能适当地做出反应。

    (3) 程序要做到界面友好,在程序运行时用户可以根据相应的提示信息进行操作。

    (4) 上传源程序到课堂派。顺序表的源程序保存为Stringindex.cpp



    #include<stdio.h>
    #include<string.h>
    #define OK 1
    #define ERROR 0
    #define MAXSIZE 255
    typedef int Status;
    typedef char ElemType; 
    //定义模式串的顺序表 
    typedef struct
    {
    	char ch[MAXSIZE+1];
    	int next[MAXSIZE+1];
    	int nextval[MAXSIZE+1];
    	int length;
    }S1String;
    //定义主串的顺序表 
    typedef struct
    {
    	char ch[MAXSIZE+1];
    	int length;
    }S2String;
    //初始化模式串 
    Status Init_S1(S1String &S1)
    {
    	S1.length=0;
    	return OK;
    }
    //初始化主串 
    Status Init_S2(S2String &S2)
    {
    	S2.length=0;
    	return OK;
    }
    //求的模式串的next 
    Status Get_S1_next(S1String &S1)
    {
    	int i=1;
    	S1.next[1]=0;
    	int j=0;
    	while(i<S1.length)
    	{
    		if(j==0||S1.ch[i]==S1.ch[j])
    		{
    			i++;
    			j++;
    			S1.next[i]=j;
    		}
    		else
    		{
    			j=S1.next[j];
    		}
    	}
    	return OK;
    }
    //求得模式串的nextval 
    Status Get_S1_nextval(S1String &S1)
    {
    	int i=1;
    	S1.nextval[1]=0;
    	int j=0;
    	while(i<S1.length)
    	{
    		if(j==0||S1.ch[i]==S1.ch[j])
    		{
    			i++;
    			j++;
    			if(S1.ch[i]!=S1.ch[j])
    			{
    				S1.nextval[i]=j;
    			}
    			else
    			{
    				S1.nextval[i]=S1.nextval[j];
    			}
    		}
    		else
    		{
    			j=S1.nextval[j];
    		}
    	}
    	return OK;
    }
    //进行比较求出结果 
    Status Compare(S1String &S1,S2String &S2)
    {
    	int i=1;
    	int j=1;
    	int result;
    	result=1;
    	while(1)
    	{
    		if(S1.next[i]==0&&S1.ch[i]!=S2.ch[j])
    		{
    			j++;
    			result=j;
    		}
    		else
    		{
    			if(S1.ch[i]==S2.ch[j])                 
    			{                                      
    				i++;
    				j++;
    			}
    			else
    			{
    				i=S1.next[i];
    				result=j-i+1;	
    			}
    			if(i>S1.length)
    			{
    				return result;	
    			} 
    		}
    	}
    }
    int main()
    {
    	char s1[255];
    	char s2[255];
    	int result;
    	S1String S1;
    	S2String S2;
    	Init_S1(S1);
    	Init_S2(S2);
    	printf("请输入模式串:");
    	scanf("%s",&s1);
    	printf("请输入主串:");
    	scanf("%s",&s2);
    	//字符数组进入主串和模式串 
    	for(int i=0;i<=strlen(s1)-1;i++)
    	{
    		S1.ch[i+1]=s1[i];
    		S1.length++;
    	}
    	for(int j=0;j<=strlen(s2)-1;j++)
    	{
    		S2.ch[j+1]=s2[j];
    		S2.length++;
    	}
    	//求结果 
    	Get_S1_next(S1);
    	Get_S1_nextval(S1);
    	result=Compare(S1,S2);
    	printf("结果是:%d",result);	
    }
    


    展开全文
  • 课本 《数据结构(C语言版)(第2版)》 严蔚敏版 前言: 这次作业写的真是一个无语,课本印刷的代码就是错的,是不是自己上课没好好听讲,老师已经修改了? P95 的KMP算法有bug。 现将通过的程序贴出来,纪念一下...


    课本 《数据结构(C语言版)(第2版)》 严蔚敏

    前言:

    这次作业写的真是一个无语昂(也怪自己基础不好),课本印刷的代码就是错的,

    是不是自己上课没好好听讲,老师都已经修改错误了?尴尬



    代码参考:

    P95 的KMP算法有bug。

    现将通过的程序贴出来,纪念一下 nextval[] 的第一个代码。


    #include <stdio.h>
    #include <string.h>
    const int MaxLength = 1e5;
    
    typedef struct {
    	char ch[MaxLength];
    	int length;
    } SString;
    SString S, T;
    char ss[MaxLength], tt[MaxLength];
    int nextval[MaxLength];
    void GetNextval();
    int Kmp(int pos);
    
    int main() {
    	int flag;
    	while(1) {
    		flag = 0;
    		printf("\t请输入主串:");
    		scanf("%s", S.ch+1);
    		S.length = strlen(S.ch+1);
    
    		printf("\t请输入模式串:");
    		scanf("%s", T.ch+1);
    		T.length = strlen(T.ch+1);
    
    		GetNextval();
    		for(int j = 1; j <= T.length; j++)
    			printf("nextval[%d] -> %d ******\n", j,nextval[j]);
    
    		flag = Kmp(1);
    		if(flag) printf("\t\t在第 %d 位匹配成功!\n", flag);
    		else printf("\t\t匹配未成功!\n");
    		printf("\n");
    	}
    	return 0;
    }
    
    void GetNextval() {
    	int i = 1, j = 0;
    	nextval[1] = 0;
    	while(i < T.length) {
    		if(j == 0||T.ch[i] == T.ch[j]) {
    			++i;
    			++j;
    			if(T.ch[i] != T.ch[j])	nextval[i] = j;
    			else nextval[i] = nextval[j];
    		} else j = nextval[j];
    	}
    
    	for(int j = 1; j <= T.length; j++)
    		printf("nextval[%d] -> %d\n", j, nextval[j]);
    }
    
    int Kmp(int pos) {//形参是匹配位置
    	int flag = 0;//标记匹配的成功与否
    	int i = pos, j = 1;
    	while(i <= S.length && j <= T.length) {
    		if(j == 0 || S.ch[i] == T.ch[j]) {
    			++i;
    			++j;
    		} else {
    			j = nextval[j];
    		}
    	}
    	if(j > T.length)
    		flag = 1;
    	if(flag)
    		return i - T.length;//匹配成功的位置
    	return 0;
    }


    展开全文
  • KMP算法 KMP算法是一个解决模式串在文本串中是否出现过,如果出现过,找出最早出现位置的经典算法 Knuth-Morris-Pratt字符串查找法,简称“KMP”算法,这个算法由DonaldKunth, Vaughan Pratt, James H.Morris三人于...
  • 数据结构与算法 -- 字符串匹配 KMP算法字符串匹配KMP算法 原理next 数组的推导KMP 算法代码实现KMP 算法优化KMP 算法优化实现 字符串匹配 题目: 给一个仅包含小写字母的字符串主串 S = abcacabdc,模式串 T = abd...
  • 本文主要针对KMP算法代码方式进行解析,首先我们要知道KMP算法的作用,是用来进行字符串匹配的,即在s串中找出与t串完全匹配的字符串,并且返回起始位置。 首先介绍字符串匹配的暴力匹配算法; 然后介绍有next...
  • KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt发现的一个字符串匹配算法; 核心思想就是: 1,先对子串进行预处理,找出前面当前位置的字母在位置之前最近的相同字母的位置,没有就是从前一个字母的的前序相似字母位置...
  • KMP算法二、源码1.暴力匹配算法2.KMP算法总结 字符串匹配问题 一、暴力匹配算法&KMP算法 KMP算法: 二、源码 1.暴力匹配算法 代码如下(示例): package Algorithm; //暴力匹配算法 思路:依次进行查找 ...
  • 关于BF算法已经优化的KMP算法
  • KMP算法之NEXT数组代码原理分析   让编程改变世界 Change the world by program   KMP算法之NEXT数组代码原理分析   NEXT数组:当模式匹配串T失配的时候,NEXT数组对应的元素指导应该用T...
  • 数据结构与算法整理3——BP算法和KMP算法 目录 数据结构与算法整理3——BP算法和KMP算法 1、字符串的基本操作 2、模式匹配——BP算法和KMP算法 3、串的操作代码(C语言) 1、字符串的基本操作 1)串的定义:...
  • KMP算法是我不想写的一个算法,原因也很简单,我可以按照算法的思路写出代码实现字符串模式匹配,但是我发现我还是不太能解释这个算法。好像有句话说的是,不能把一个东西解释给别人听,本质上还是没有完全理解。...
  • 一、KMP算法之Next数组代码原理分析  1.Next数组定义  当模式匹配串T失配的时候,Next数组对应的元素指导应该用T串的哪个元素进行下一轮的匹配。  我们会发现,匹配串T下标为1位置的next数组的值总为0,...
  • 文章目录1、应用场景2、暴力匹配算法2.1 案例展示2.2 时间复杂度分析2.3 代码实现2.4 KMP算法对暴力匹配的改进3、 KMP算法3.1 算法原理 1、应用场景   Knuth-Morris-Pratt 字符串查找算法,简称为 KMP算法,常用于...
  • KMP算法之NEXT数组代码原理分析 让编程改变世界 Change the world by program KMP算法之NEXT数组代码原理分析 NEXT数组:当模式匹配串T失配的时候,NEXT数组对应的元素指导应该用T串的哪个元素进行下一轮的...
  • KMP算法之next数组代码原理分析 KMP算法之实现及优化 7.1字符串 7.1.1 定义 串(string)是由零个或多个字符组成的有限序列,又名叫字符串。 一般记为 s = “a1a2a3……an” (n&amp;amp;amp;amp;gt;0...
  • 前言 本篇博客主要是给出KMP算法的模板,所适应的读者都是接触过数据结构中KMP算法的人...//KMP算法代码模板 //获取next数组 int get_next(char T,int *next){ int i,j; i=1; j=0; next[i]=0; while(i<T[0]){
  • 数据结构+KMP算法

    2019-03-16 20:15:58
    1.KMP算法 next数组从0开始 代码如下: #include&amp;amp;lt;cstdio&amp;amp;gt; #include&amp;amp;lt;cstring&amp;amp;gt; #include&amp;amp;lt;vector&amp;amp;gt; #include&amp;amp;...
  • 对于本文的KMP算法,你需要看看这些文章《数据结构作业之串实现通信录》《KMP算法之next数组的简便求解》。另外,对于本文的代码,是摘抄自书上的,没有什么可讲的,要是不懂的话,自己看数据结构的书来理解吧。先看...
  • C++ 数据结构kmp算法中的求Next()函数的算法 实例代码: #include using namespace std; void preKmp(char *c, int m, int Next[]) { int i=1,j=-1; Next[0]=-2; while(i<m) { if(j==-2) { Next[i]=-1...
  • 什么是模式匹配、常见模式匹配算法及C/C++/Java代码 详见...KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KM...

空空如也

空空如也

1 2 3 4 5 ... 18
收藏数 354
精华内容 141
关键字:

数据结构kmp算法代码

数据结构 订阅