Chinaunix首页 | 论坛 | 博客
  • 博客访问: 528510
  • 博文数量: 102
  • 博客积分: 3165
  • 博客等级: 中校
  • 技术积分: 1232
  • 用 户 组: 普通用户
  • 注册时间: 2009-05-09 16:38
文章存档

2016年(1)

2013年(14)

2012年(6)

2011年(22)

2010年(57)

2009年(2)

我的朋友

分类: C/C++

2013-09-06 11:40:14

1 KMP
KMP是一种高效的字符串查找算法,主要用于在主串中查找一个特定字串(模板)出现的位置(或是否出现)。
朴素字符串查找算法主要是通过逐次比较来实现的,在主串中找到一个位置I和字串起始字符一样时,便顺次比较后续字符。若匹配成功,则输出相应结果。若不匹配,则从位置I的下一个位置I+1开始比较。若主串长度为M,字串长度为N的最多需要比较M*N次。
KMP比较主要的改进是,充分利用已经比较的结果和字符串的性质,在发生不匹配时,不再单纯后移一个位置,而是可能跳过多个位置重新开始比较,因此效率大为提升。
所谓利用已经比较的结果,可以通过一个简单的例子来理解。当一个字符串形如ABCDEFG,即完全没有重复的字符出现时,当比较到某一位置如F,发生不匹配时,此时匹配的部分是ABCDE,则我们可以完全跳过主串的ABCDE部分,即偏移5后再继续比较,而不再像朴素查找算法每次后移一个位置,因此效率大为提升。
所谓利用子串自身性质时,我们要根据字符串自身的特点来决定每次不匹配发生时,偏移多少再继续开始比较。这里有两个标准,第一不遗漏任何可能匹配的情况,第二效率尽可能提升。对于子串来说不是所有字符串都是形如ABCDEFG格式,没有重复,因此也不能单纯地不匹配发生时,就偏移已匹配字符串长度个位置再开始比较。为了合理确定这个偏移大小,我们引入了一个覆盖值的概念,这也是KMP算法的核心。
所谓覆盖值是指一个字符串首尾是否存在一摸一样的的子串,若有相应子串则其长度为覆盖值。
例如ABCDEFG,在位置F发生不匹配时,已匹配的部分是ABCDE,它的覆盖值为0,因为对于ABCDE这个字符串,它的首尾没有一样的子串。
再例ABCABFG,在位置F发生不匹配时,已匹配的部分是ABCAB,它的覆盖值为2,因为对于ABCAB这个字符串,它的首尾存在一样的子串“AB”,其长度为2。//ABCABCA的覆盖值为4,AAAAAA的覆盖值为5。
当发生不匹配时,已匹配部分的字符串为S,S的长度为L,S的覆盖值为F,则偏移量为L-F。
覆盖值为0时,形如我们最开始提到的ABCDEFG,此时偏移量为L-F = L,即偏移整个已匹配部分的长度,与最初的结论一致。

阅读(1568) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~