频道栏目
IT货架 > > 正文
(转载)KMP算法
网友分享于:Jan 1, 1970 8:00:00 AM    来源: IT货架   
(转载)http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html                                                              KMP算法         在介绍KMP算法之前,先介绍一下BF算法。 一.BF算法     BF算法是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果。     举例说明:     S:  ababcababa     P:  ababa   BF算法匹配的步骤如下            i=0                                   i=1                             i=2                         i=3                          i=4   第一趟:ababcababa         第二趟:ababcababa      第三趟:ababcababa    第四趟:ababcababa    第五趟:ababcababa              ababa                            ababa                          ababa                        ababa                       ababa             j=0                                   j=1                            j=2                         j=3                         j=4(i和j回溯)                 i=1                                 i=2                           i=3                            i=4                        i=3  第六趟:ababcababa         第七趟:ababcababa       第八趟:ababcababa     第九趟:ababc
相关板块推荐

广告服务联系QQ:1134687142 | 网站地图

版权所有: IT货架- 内容来自互联网,仅供用于技术学习,请遵循相关法律法规. 京ICP备11030978号-1