一种改进的KMP算法

Improved KMP algorithm

在给出改进的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.