对KMP算法的一个改进

Improvement of KMP Algorithm

ＫＭＰ算法是串匹配算法中效率最高的算法，然而其存在着正文字符与模式中多个相同字符重复比较的缺陷．本文对ＫＭＰ算法加以改进，建立新型自动机ＮＥＷＫ．新自动机ＮＥＷＫ将旧自动机中指向相同字符的走向改道，从而避免字符的重复匹配，使算法具有更高的效率．

Famous KMP algorithm possesses the characteristic of the highest efficiency in algorithms for pattern matching in string. However, there is a defect of the repeated comparison of a character in the text with the same characters in the pattern in KMP algorithm. This paper improves KMP algorithm and establishes a new automat NEWK. The NEWK changes the course of the same characters in old automat, thereby it avoids the repeated comparsion of characters and increases matching efficiency of the algorithm largely.