一种改进的KMP算法  

Improved KMP algorithm

作　　者：俞松[1] 郑骏[1] 胡文心[1] 

机构地区：[1]华东师范大学计算中心,上海200062

出　　处：《华东师范大学学报（自然科学版）》2009年第4期92-97,共6页Journal of East China Normal University(Natural Science)

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

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

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]