下载  >  课程资源  >  C/C++  > 匹配算法之KMP.docx

匹配算法之KMP.docx 评分

此文件用于kmp字符匹配算法,对于初学者很有好处

...展开详情
所需积分/C币:0 上传时间:2014-03-02 资源大小:23KB
举报 举报 收藏 收藏
分享 分享
《数据结构》实验报告 涉及客房管理系统、串模式匹配算法、KMP算法及改进算法、二叉树节点路径

实验一 客房管理(链表) 实现功能:以带表头结点的单链表为存储结构,实现如下客房管理的设计要求。 实验二 串模式匹配算法(串) 实现功能: 从主串中第K个字符起,求出子串在主串中首次出现的位置,即模式匹配或串匹配。 要求用三种模式匹配算法分别实现: 朴素的模式匹配算法(BF算法) KMP改进算法(Next[ ]) KMP改进算法(NextVal[ ]) 实验三 求二叉树上结点的路径(二叉树) 实现功能:在采用链式存储结构存储的二叉树上,以bt指向根结点,p指向任一给定的结点,编程实现求出从根结点bt到给定结点p之间的路径。 快毕业了,留一点东西给学弟们吧!

立即下载
字符串匹配算法KMP算法

一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。

立即下载
数据结构-KMP算法的实现.

帮助了解KMP算法 KMP算法是对一般模式匹配算法的改进,由D.E.Knuth与V.R.Pratt和J.H.Morris 同时发现的因此人们称它为克努特-莫里斯-莫拉特操作(简称为KMP算法)。

立即下载
串匹配-KMP算法

kmp算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息

立即下载
基于KMP思想的模式匹配算法及vc++实现

一种改进的字符串匹配算法,由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现,简称KMP。关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现的关键是next函数。简述分词算法之正向最大匹配法。

立即下载
kmp算法匹配子串vc++6.0

基于c语言实现。作为一个IBM的研究人员,请写一个程序找出给定的DNA片段之间的相同之处,使得对个体的调查相关联。 一个DNA碱基序列是指把在分子中发现的氮基的序列给罗列出来。有四种氮基(A 腺嘌呤、 T 胸腺嘌呤、 G鸟嘌呤、 D胞嘌呤),例如,一个6碱基DNA序列可以用TAGACC来表示 给出一个DNA碱基序列的集合,确定在所有序列中都出现的最长的碱基序列

立即下载
KMP算法的实现

《数据结构》课程实验,KMP算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的,此算法可以在O(n+m)的试卷数量级上完成串的模式匹配操作。

立即下载
Knuth-Morris-Pratt(KMP)算法(字符串匹配)

参考许多资料之后翻译整理的好论文!让你迅速透彻的理解KMP算法! [1] http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm [KMP 77]D.E. Knuth, J.H. Morris, V.R. Pratt: Fast Pattern Matching in Strings. SIAM Journal of Computing 6, 2, 323-350 (1977) [2] http://www.cse.iitk.ac.in/users/dsrkg/cs210/applets/strMatching/KMP

立即下载
字符串的模式匹配算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高

立即下载
一种改进的字符串匹配算法

一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。

立即下载
数据结构拓展——KMP算法

在朴素的模式匹配算法中,当目标串和模式串的字符比较不相等时,进行下一次比较的 是目标串本趟开始处的下一个字符,而模式串则回到起始字符,这种回溯显然是费时的。如 果仔细观察,可以发现这样的回溯常常不是必须的。 由 D.E.Knuth、J.H.Morris 和 V.R.Pratt 三人共同提出了一个改进的模式匹配算法,称为 KMP 算法。当某一位匹配失败时,可以根据已匹配的结果进行判断。当模式串中的第 k 位 与目标串的第 i 位比较发生不匹配时,需要将模式串向右滑动到哪里继续与目标串的第 i 位 进行比较?即目标串始终无须回溯,模式串返回到前面的什么位置,视情况而定。如图 4-4 所示的例子。K

立即下载
KMP算法c语言实现

#include <stdlib.h> #include<stdio.h> #include <string.h> typedef struct { int length; char *p; }sstring; int *get_next (sstring s1) { int m = s1.length; char *p=s1.p; int j = 0; int *x=(int *)malloc(m*sizeof(int)); x[1] = 0; int i = 1; printf("%4d",x[

立即下载
数据结构课程设计-kmp算法

KMP算法是对一般模式匹配算法的改进,由D.E.Knuth与V.R.Pratt和J.H.Morris 同时发现的因此人们称它为克努特-莫里斯-莫拉特操作(简称为KMP算法)。 对于一般的模式匹配算法:分别利用两个指针i和j指示主串S和T中的当前正待比较的字符位置。算法的基本思想是:从主串的S的第POS个字符开始起和模式的第一个字符比较之,如相等,则继续逐个比较后续字符;否则从主串的下一个字符起再重新和模式的字符比较之。以此类推,直到模式T中的每个字符依次和主串S中的一个连续字符序列相等,则称匹配成功,则函数值为和模式T中的第一个字符相等的字符在主串S中的序号,否则称匹配不成功,函数值为0.而对

立即下载
模式匹配的一种改进方法kmp

这种改进算法是D.E.Knuth 与V.R.Pratt 和J.H.Morris 同时发现的,因此人们称它为 克努特-莫里斯-普拉特算法(简称为KMP 算法)。该算法可以在O(n+m)的时间数量级上完成 串的模式匹配操作。其改进在于:每当一趟匹配过程中出现字符比较不等时,不需回溯i 指针,而是利用已经得到的‘部分匹配’的结果将模式向右‘滑动’尽可能远的一段距离后, 继续进行比较。

立即下载
克努特——莫里斯——普拉特操作(简称KMP算法)

kmp算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息

立即下载
数据结构课程设计实验报告-KMP算法的实现

KMP算法是对一般模式匹配算法的改进,由D.E.Knuth与V.R.Pratt和J.H.Morris 同时发现的因此人们称它为克努特-莫里斯-莫拉特操作(简称为KMP算法)。 对于一般的模式匹配算法:分别利用两个指针i和j指示主串S和T中的当前正待比较的字符位置。算法的基本思想是:从主串的S的第POS个字符开始起和模式的第一个字符比较之,如相等,则继续逐个比较后续字符;否则从主串的下一个字符起再重新和模式的字符比较之。以此类推,直到模式T中的每个字符依次和主串S中的一个连续字符序列相等,则称匹配成功,则函数值为和模式T中的第一个字符相等的字符在主串S中的序号,否则称匹配不成功,函数值为0.而对

立即下载
高效算法:竞赛、应试与提高必修128例.[法] Christoph Dürr Jill-Jênn Vie(带书签文字版).pdf

本书旨在探讨如何优化算法效率,详细阐述了经典算法和特殊算法的实现、应用技巧和复杂度验证过程,内容由浅入深,能帮助读者快速掌握复杂度适当、正确率高的高效编程方法以及自检、自测技巧,是参加ACM ICPC、Google Code Jam等国际编程竞赛、备战编程考试、提高编程效率、优化编程方法的参考书目。 作者简介 Christoph Dürr,法国国家科学研究院研究员,巴黎皮埃尔-玛丽·居里大学博士生导师,Operation Research科研组研究主任。 Jill-Jênn Vie,法国高等电力学院博士、算法讲师,担任法国高等师范学院Paris-Saclay团队在ACM竞赛中的算法导师;曾

立即下载
ACM算法竞赛常用代码

时间复杂度(渐近时间复杂度的严格定义,NP问题,时间复杂度的分析方法,主定理)   排序算法(平方排序算法的应用,Shell排序,快速排序,归并排序,时间复杂度下界,三种线性时间排  序,外部排序)   数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同余方程,中国剩余定理) 指针(链表,搜索判重,邻接表,开散列,二叉树的表示,多叉树的表示) 按位运算(and,or,xor,shl,shr,一些应用) 图论(图论模型的建立,平面图,欧拉公式与五色定理,求强连通分量,求割点和桥,欧拉回路,AOV问题,AOE问题,最小生成树的三种算法,最短路的三种

立即下载