论文模式匹配算法和实现是关于本文可作为模式匹配算法方面的大学硕士与本科毕业论文模式匹配算法论文开题报告范文和职称论文论文写作参考文献下载。
摘 要：模式匹配是字符串的基本运算之一,也是数据结构课程的重点算法之一.在当今文本信息海量增长的时代,如何快速地定位就显得尤为重要.该文通过朴素模式匹配算法与KMP算法的比较说明各自的优缺点,同时通过提高获取next数组的效率,加快KMP算法的匹配速率.
关键词：模式匹配；KMP；NEXT函数；文本搜索
中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2017）18-0025-02
从计算机诞生至今,文本信息海量地增长,无论是在金融、航海、DNA检测、网络入侵等领域都需要在文本中快速地查找所需要的信息,因此设计出一个好模式匹配算法,不公可以高效地进行定位,还可以提高文本编辑能力,提高改善人类的生活.
模式匹配即子串的定位操作,是数据结构中逻辑结构为串的最重要操作之一.该算法的主要目的是找出特定的模式串在一个较长的字符串中出现的位置.如有两个字符串T称为模式串,字符串s称为主串,找出模式T在主S中的首次出现的位置.一旦模式T在目标s中找到,就称发生一次匹配.例如,目标串S等于’ababeabcaebab’,模式串T等于’abcac’,则匹配结果为6,其中经典的模式匹配算法包括朴素匹配算法、KMP.
1朴素模式匹配算法
朴素模式匹配算法的基本思想是在模式串T和主串S中,使用循环变量I,j,分别在模式串和主串中循环跑动,如果模式串与主串对应字符相等S[i]等于T[j],则同时后移；如果模式串与主串对应字符不相等S[i]≠[j],则模式串回滚到起始位置,而主串回滚到起始位置的下一个字符.如此一直循环直至主串结束或模式串结束.朴素模式匹配算法的回溯演示如下：
算法流程图描述如下：
2 KMP算法
与朴素模式匹配算法比较,KMP算法最大的特点是模式串在匹配不相等的情况下,不再回溯,而是匹配串进行滑动,所以匹配串滑动的位置是算法的关键.由于模式串已匹配的字符串与主串已匹配内容相同,从模式串部分匹配字符中从前和从后数的字符串如果相同,即相同字符串无需再进行匹配,即模式串滑动的位置为相同字符数加1.滑动演示如下：
4总结
本文通过分析朴素匹配算法与KMP算法如何进行字符串比较,在比较相等与不相等时模式串与主串如何移动,说明两者的优缺点,并且在KMP算法中通过改進next函数值的计算,提高KMP匹配效率,并通过上机验证实现算法.
总结:这是一篇与模式匹配算法论文范文相关的免费优秀学术论文范文资料,为你的论文写作提供参考。
参考文献：
1、 基于ORB特征点匹配多目标跟踪算法 摘 要：视频中的多目标跟踪是计算机视觉领域的一个重要问题 针对多目标跟踪过程中由于目标缩放、旋转、扭曲以及遮挡等问题的存在导致目标易丢失的问题，。
2、 模板匹配下的限速交通标志识别算法 摘要：为实现限速交通标志的快速准确识别，采用模板匹配对限速交通标志进行识别。首先图像进行倾斜校正，并在HSV颜色空间进行分割，提取感兴趣区域（R。
3、 程序代码抄袭检测中串匹配算法 【 摘 要 】 为了保证程序设计课程实践教学质量，避免学生抄袭，可以检测学生的源程序，代码的相似度是抄袭检测的关键技术。文章介绍了一种串匹配算法。
4、 基于改进多块局部二进制模式的人眼定位算法 摘 要： 人眼定位是人脸识别系统中必须解决的问题，为了提高人眼定位的精确度和速度，提出一种基于改进多块局部二进制模式的眼睛中心定位算法。该算法构。
5、 FFT捕获算法部分匹配滤波器长度选取 摘要： 高动态环境下具有较大的多普勒频移， 不利于信号的快速捕获。 基于PMFFFT的快速捕获算法利用部分匹配滤波器结合FFT运算的方法可实现扩。
6、 基于港口物流人岗匹配视角下对高职人才培养模式 摘要：目前港口物流企业普遍存在的人力资源管理问题，就其提出相应的优化策略，科学地做好国际港口物流的人力资源开发和管理。同时通过对人岗匹配度的研究。