资源描述：
中国矿业大学学报990 2 2 9 中国矿业大学学报 JO U RNA L O F CH INA U NIVERSIT Y O F M I NING b e g i n j ∶ 1; i ∶ 0 ; NEW K ［1］∶ 0 ; w h i l e j m d o b e g i n w h i l e i 0 a n d b ［j ］ b ［i ］ d o i ∶ NEW K ［i ］; j ∶ j 1; i ∶ i 1; NEW K ［j ］ ∶ i e n d ; j ∶ 1; w h i l e j m d o b e g i n j ∶ j 1; i f b ［j ］ b ［NEW K ［j ］］ t h e n NEW K ［j ］∶ NEW K ［NEW K ［j ］］ e n d e n d ; f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 2 / 990 2 2 9. h t m （第 3／5 页）2 0 10 -3-2 3 15 57 30 中国矿业大学学报990 2 2 9 由上面算法构造的模式b a b a b c 和a a a ⋯a 的新自动机如图3，4. 图3 模式b a b a b c 的新自动机 Fi g . 3 Ne w a u t o m a t o n o f p a t t e r n b a b a b c 图4 模式a a a ⋯a 的新自动机 Fi g . 4 Ne w a u t o m a t o n o f p a t t e r n a a a ⋯a 由图可看出, 由NEW K 构造的新自动机, 不存在b j b NEW K j 的现象, 因而更加简洁、清晰, 避免 了一个正文字符与模式中多个相同字符反复匹配的情形, 从而提高了效率. 3 时间复杂度分析 文献［1］中已给出了K M P算法的时间复杂度, 它在最坏情况下为O m n , 计算K j 的复杂度为 O m . 本文将计算K j 改为计算NEW K j , 其中增加m 次字符比较, 其时间复杂度仍为O m . 因此, 从整 体上讲, 在最坏情况下的时间复杂度并不能被降低, 仍为O m n . 但在实际应用中, 将随模式B中类似 子串的多少, m 与n 的大小悬殊等情况, 复杂度的降低各有所不同. 例如对模式B b a b a b c , 若正文A b a b a c b a b a c b a b a b c , A 的长度是16 . 则使用K j 自动机, 匹配过程中 需要2 0 次字符比较. 而用新自动机, 只需要16 次. 又如对模式B a a a a , 若正文A a a a b a a a c a a a d a a a a , A 的长度为16 . 则使用K j 自动机, 匹配过程中需要 2 5次字符比较. 而用新自动机, 只需要16 次. 而若A a a a b a a a b ⋯a a a b a a a a , A 的长度为4n . 则用K j 自动机需 要7 n -3次, 而用新自动机, 只需4n 次. 从上面的例中可看出, 对于有较多相同子串的模式B, m 与n 的悬殊越大, A 中相似于B的子串越多, 则节省的比较次数越多, 效率提高得越多. f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 2 / 990 2 2 9. h t m （第 4／5 页）2 0 10 -3-2 3 15 57 30 中国矿业大学学报990 2 2 9 4 结束语 S. A . CO O K 于197 0 年在理论上证明了模式匹配问题可在O m n 时间内解决. 在有名的3个串匹配 算法 K M P，BM 和RK 算法中, 只有K M P串匹配算法达到了在最坏情况下时间复杂度为O m n . 所以, K M P算法是最经济的算法. 而经本文对K j 的改进, 使构造出的新自动机更简洁, 更清晰, 从而使改造 后的K M P算法具有更高的匹配效率. 尤其考虑到在很多情况下, 模式B与正文A 总是有方方面面的联 系的, 且一般总有m n , 因而在实际应用中, 只要模式B中有较多的类似子串, 则改进后的K M P算法都将 比原K M P算法在时耗上有很大幅度的降低. 作者简介 姜利群，女，1956 年生，讲师 作者单位 中国矿业大学计算机系 徐州 2 2 10 0 8 参考文献 1 卢开澄. 计算机算法导引设计与分析. 北京清华大学出版社, 1996 . 2 2 1～2 2 4 2 吴哲辉，曹立明，蒋昌俊. 算法设计与分析. 北京煤炭工业出版社，1993. 141～145 收稿日期 1998 -0 5-19 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 2 / 990 2 2 9. h t m （第 5／5 页）2 0 10 -3-2 3 15 57 30
展开阅读全文
