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，即偏移整个已匹配部分的长度，与最初的结论一致。
阅读(1675) | 评论(0) | 转发(0) |
