频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
模式串匹配--KMP算法
2015-04-22 08:45:31           
收藏   我要投稿
 前几天百度LBS部门实习二面,让写一个字符串匹配函数,当时忘记KMP怎么写了,就默默的写了一个暴力搜索,连尝试推导一下KMP都没有,结果自然是没有过,以后面试要多和面试官交流,就算忘记了,也要让他知道你试图推导,要不然他会觉得你可能都没有听过。

 

  KMP是对前缀暴力搜索的改进,基于的想法其实是很朴素的。首先我们来看一下暴力搜索。

 

 

char* BF(char *src, char *pattern){

    if(src == NULL || pattern == NULL) return NULL;

    char *src_temp = src, *pattern_temp = pattern;

    while(*src_temp != '\0' && *pattern_temp != '\0'){

        if(*src_temp == *pattern_temp){

            src_temp++; pattern_temp++;

        }else{

            src_temp = ++src;

            pattern_temp = pattern;

        }

    }

    if(*pattern_temp == '\0') return src;

    else return NULL;

}

 

  如果匹配失败,则将关键字向右滑动一个字符,从头开始匹配关键字,匹配成功则有src[i,i+1,......i+m] == p[0,1,......m]。BF的时间复杂度是O(m*n)。KMP改进的想法很朴素,能不能不是每次移动一个距离,每次多移动几个距离不就可以提高效率了么,但是每次多移动几个呢?KMP算法就是解决每次移动几个的问题。

 

  假设暴力搜索时关键字在匹配到p[j]字符时失败了,即src[i,i+1,......,i+j-1] == p[0,1,......j-1](1), src[i+j] != p[j],则按照暴力搜索的方法将关键字向右滑动一个字符,即从src[i+1]开始从新匹配。

 

但是我们假设关键串有如下特征:

 

p[0,1.....j-2] != p[1,2,......j-1](2),则(1)可知p[0,1......j-2] != src[i+1,i+2,......,i+j-1],所以将关键串向右滑动一个字符从src[i+1]开始匹配肯定失败,所以在我们知道(2)式的情况下,就可以直接跳过向右滑动一个字符,那到底滑动几个字符呢?如果我们知道了子串p[0,1,......next(j-1)](next(j-1)又叫做j-1的失效函数),既是p[0,1,......j-1]的最长真前缀又是p[0,1,......j-1]最长后缀,那我们就可以将关键字向右滑动j-1-next(j-1)个字符,并且认为关键串的前next(j-1)个字符已经匹配成功,继续从src[j]开始匹配(这个思想同样应用于求next(j)的算法中,后面的代码中可以看到)。所以整个KMP算法的关键就是求得每一个next(j), j = 0......m,这样就可以知道在j+1匹配失败的时候,应该将关键字向右滑动几个字符位置。可以证明KMP算法的时间复杂度是O(m+n)。

 

求next(j)的代码如下,相关解释会在注释中:

 

 

void next(char *pattern, int *next){
    int t = -1; next[0] = -1;
    for(int s = 0; pattern[s+1] != '\0'; s++){
        while(t > -1 && pattern[t+1] != pattern[s+1]) t = next[t];// t是最长真前缀的下标,s是字符串的下标,这其实就是一个真前缀和后缀的匹配过程,匹配失败则回溯真前缀的真前缀。这也就是KMP的核心思想。
        if(pattern[s+1] == pattern[t+1]){
            t = t + 1;
            next[s+1] = t;
        }else  next[s] = -1;
    }
}

 

 

得到上面的next(j)后,就可以在O(n)的时间内扫描src字符串,以判断该关键串是否出现在其中。关键串沿着匹配字符串滑动,不断尝试将关键字的下一个字符与被匹配字符串的下一个字符匹配,逐步推进。如果在匹配了j个字符后无法匹配,那么将关键字向右滑动j-next(j)个位置,并且前next(j)个字符已经匹配成功,从src[j+1]继续匹配。

 

char* KMP(char *src, char *pattern){
    if(src == NULL || pattern ==  NULL) return NULL;
    int pattern_size = 0;
    for(; pattern[pattern_size] != '\0'; pattern_size++)
    int* next = new int[pattern_size];
    next(patter,next);
    int s = -1;
    for(int i = 0; src[i] != '\0'; i++){
        while(s > -1 && src[i] != pattern[s+1]) s = next[s];//匹配失败,则将关键串向右滑动s - next[s]个字符,并且前next[s]个字符已经匹配成功,继续从src[i]开始匹配。
        if(src[i] == pattern[s+1]){
            s++;
        }
        if(pattern[s+1] == '\0') return &src[i] - pattern_size +1;
    }
    return NULL;
}

 

 

说到KMP就不得不说AC自动机,其实理解了KMP的思想,即找出子串p[0,1,......next(j-1)],既是p[0,1,......j-1]的最长真前缀又是p[0,1,......j-1]最长后缀,也就不难理解AC自动机。AC自动机又叫Aho-Corasick算法,是Aho和Croasick对KMP算法的推广,可以在一个文本串种识别一个关键字集合中的任何关键字。由于是关键字集合,所以采用了trie-tree来存储关键字,每个节点的失效函数稍微不同于KMP的失效函数,即状态next(j)对应于最长的、既是串pattern[0,1......,j]的后缀,又是某个关键字的前缀的字符串。对于AC自动机,你可以理解为是在求失效函数和匹配过程中考虑了关键字集合的KMP或者KMP是AC自动机的特例,但是核心思想就是子串p[0,1,......next(j-1)],既是p[0,1,......j-1]的最长真前缀又是p[0,1,......j-1]最长后缀,AC自动机只是描述关键字集合的一种方法。关于AC自动机,DSQiu的博客http://dsqiu.iteye.com/blog/1700312有一个比较好的实现,有兴趣可以看一下。

点击复制链接 与好友分享!回本站首页
相关TAG标签 算法 模式
上一篇:关于A*寻路算法的认识
下一篇:自定义圆形滚动条(透明效果)--利用开源项目ProgressWheel
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站