KMP模式匹配算法的研究分析

• 作者: 杨战海
• 来源期刊: 计算机与数字工程
• 学科: 工学
• 关键词: 模式匹配 KMP算法 算法 next函数
• 年，卷（期）: 2010,（5）
• 所属期刊栏目: 算法与分析
• 页码范围: 38-41
• 分类号: TP301
• 字数: 3008字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-9722.2010.05.012

摘要

通过对字符串模式匹配算法和KMP算法的研究,分析了一种改进KMP算法的方法,并通过对算法的复杂性进行计算,结果表明,改进后的KMP算法和KMP算法的时间复杂度均为O(m+n),但改进后算法的平均比较次数约为未改进算法的平均比较次数的0.833倍,因此改进后的KMP算法更能提高字符串模式匹配的工作效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨战海	延安大学计算中心	26	56	3.0	7.0