华东师范大学学报(自然科学版) ›› 2009, Vol. 2009 ›› Issue (4): 92-97.

• 计算机科学 • 上一篇    下一篇

一种改进的KMP算法

俞松，郑骏，胡文心   

  1. 华东师范大学 计算中心, 上海200062
  • 收稿日期:2008-10-05 修回日期:2009-01-23 出版日期:2009-07-25 发布日期:2009-07-25
  • 通讯作者: 郑骏

Improved KMP algorithm

YU Song,ZHENG Jun,HU Wenxin

  

  1. Computer Center, East China Normal University ，Shanghai200062, China
  • Received:2008-10-05 Revised:2009-01-23 Online:2009-07-25 Published:2009-07-25
  • Contact: ZHENG Jun

PDF

1706

摘要： 在给出改进的KMP模式匹配算法的定义和步骤的同时,对其进行了严格推导和证明.实验证明,当模式首次出现在文本后半段的情况下,该算法较原KMP算法具有更少的比较次数和更高的效率.

关键词: 匹配, 模式, 串, 时间复杂度, 文本, 匹配, 模式, 串, 时间复杂度, 文本

Abstract: This paper established an improved KMPalgorithm for pattern matching in string. Tests proved that the algorithm has less comparison times and higher efficiency under the circumstances that the pattern first appears in the bottom half of a text string.

Key words: pattern, string, time complexity, text , match, pattern, string, time complexity, text

中图分类号: