资源描述：
《字符串匹配算法的研究-本科论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、字符串匹配算法的研究及其程序实现计算机学院计算机科学与技术专业2007级指导教师：滕云摘要：在字符串匹配算法Z中，最古老和最著名的是由D.E.Knuth,J.h.Morris,V.R.Pratt在1997年共同提出的KMP算法。直至今日，人们对字符出匹配问题述在进行着大量的研究，以寻求更简单，或者平均时间复杂度更优的算法;学者们在不同的研究方向上，设计出了很多冇效的匹配算法。在现实生活中，吊匹配技术的应用十分广泛，其主要领域包括：入侵检测，病毒检测，信息检索，信息过滤，计算生物学，金融检测等等。在许多应用系统小，串匹配所占的时间比重相当大，因此，串匹配算法的速度很大程度上影响着整个系统
2、的性能。该论文重点分析了KMP算法的实现原理和C语言实现，并在此基础上提出了改进的KMP算法，使得该算法更方便实用。关键词：KMP算法；时间复杂度；串匹配；改进；方便使用；StringmatchingalgorithmandImplementationoftheProgramCollegeofComputerSciences,ComputerScienceandTechnologyProfessionalgrade2007,InstructorYunTengAbstractor:Amongthestringmatchingalgorithm,theoldestandmostfamous
3、isKMPalgorithmco-sponsoredbyD.EKnuth,J.h.Morris,VRPrattin1997.Asoftoday,alotofresearchtoStringmatchingarestillinprogress,toseekamoresimplyorbetteraveragetimecomplexityofthealgorithm.Indifferentresearchdirection,scholarshavedesignedalotofvalidmatching.Inreallife,thestringmatchingtechniqueiswidely
4、used.Themainareasinclude:intrusiondetection,virusdetection,informationretrieval,informationfiltering,computationalbiology,financialinspectionandsoon.Inmanyapplications,alargepercentageofthetimewasplacedbythestringmatching,sothestringmatchingalgorithmssignificantlyaffectthespeedperformanceofthewh
5、olesystem.ThepaperanalyzestheimplementationoftheKMPalgorithmtheoryandthroughtheClanguagetoachieveit.AndweputsforwardamodifiedKMPalgorithminordertomakesthealgorithmmoreconvenientandpractical・Keywords:KMPalgorithm;Timecomplexity;Stringmatching;Improved;Easytouse;目录摘要1ABSTRACT1第一章弓I言3第一节：字符串匹配研究的目的
6、和意义3第二节：本文的内容和安排3第二章串匹配算法的概念与研究现状4第一节：字符串匹配的有关概念4第二节：字符串匹配算法的研究现状4第三章KMP算法和BM算法及其改进算法的研究及实现5第一节：KMP算法的研究及实现5第二节：KMP算法改进及其程序实现8第四章总结和展望12第一节：总结13第二节:展望13参考文献14致谢14第一章：引言第一节：字符串匹配研究的目的和意义字符串是计算机科学中常见的基本概念,搜索问题也是计算机科学中的基本问题。而且迄今为止文本信息仍然还是最主要的信息交换手段之一，因此作为文本处理中的一个重要领域——字符串匹配，就显得尤其的重要，随着互联网的日渐庞人，信息也是
7、越來越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在；在这其中，字符串匹配算法起着非常重要的作用，一个高效的字符吊匹配算法，可以极大的提高搜索的效率和质量。木文力图阐明字符串匹配算法的发展过程中的两个重要的算法KMP算法和BM算法，并且并介绍了各个算法的特点，并给予了适当的比较和分析，进而提出了新的字符串匹配算法希望能够在各方面有所改进。字符串匹配技术冇着十分广泛的应用领域，它的最直接的应用领域是构建数据的全文检索系统和图
