字符串查找KMP算法(转)-阿里云开发者社区

开发者社区> developerguy> 正文

字符串查找KMP算法(转)

简介: 如果你用过ctrl+F这个快捷键,那么你有很大的概率使用过这个算法,这就是在待查找字符串(可能有成千上万个字符)中找出模式串(比较小,可能有几个字符),可能找到大于或者等于1次的位置。例如,在ababcd中找出abc。
+关注继续查看

如果你用过ctrl+F这个快捷键,那么你有很大的概率使用过这个算法,这就是在待查找字符串(可能有成千上万个字符)中找出模式串(比较小,可能有几个字符),可能找到大于或者等于1次的位置。例如,在ababcd中找出abc。这里介绍算法思想,只给出了第一次出现的位置。

一.算法思想

传统算法是从匹配串第一字符开始和模式串比较,直到遇到不符合的字符,然后从匹配串的下一个字符开始,重复上面的过程。代码如下:

复制代码
void find(char t[],char p[]){
    int m = strlen(t);
    int n = strlen(p);
    int i,j,k;//k:匹配串下标,j:模式串下标
    for(k=0;k<m;k++){
        j = 0;
        i = k;
        while(j<n){
            if(p[j]==t[i]){
                i++;
                j++;
            }else{
                break;
            }
        }
        if(j==n){
            printf("在%d处匹配\n",k);
            break;
        }
    }
}
复制代码

 

 KMP算法是这中算法的改进,在于不是i不是每次都移动一个位置,而是尽可能多的向后移动从而提高匹配效率。到底移动多少个位置,这就是KMP算法的关键。KMP算法维护了一个和模式串长度相同的数组,这个数组表示当前匹配到底最大前缀长度。比如abacab的最大前缀长度就是2,分别是前缀ab,后缀ab。而数组next就是[0,0,1,0,1,2],可以利用这个信息直接跳过已经匹配到的前缀。

二.算法实现

 

复制代码
void makeNext(char p[],int next[]){
    int q,k;//k是最大前缀长度,q是匹配串下标
    next[0] = 0;
    for(q=1,k=0;q<strlen(p);q++){
        //若果不相等,那么就从上一次个字符串最长前缀处查看,依次类推
        while(k>0&&p[q]!=p[k]){
            k = next[k-1];
        }
        if(p[q]==p[k]){
            k++;
        }
        next[q] = k;
    }
}
void kmp(char t[],char p[]){
    int next[3] = {0};
    makeNext(p,next);
    int i=0,j=0;//i是匹配串的下标,j是模式串的下标
    while(i<strlen(t)&&j<strlen(p)){
        //如果相等就继续比较
        if(j==0||p[j]==t[i]){
            i++;
            j++;
        }else{//不相等就要跳跃
            j = next[j-1];
        }
    }
    if(j>=strlen(p)){
        printf("模式串匹配在%d处\n",i-j);
    }else{
        printf("匹配失败了");
    }
}

http://www.cnblogs.com/bdbk/p/5202482.html

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
计算字符串相似度算法——Levenshtein
0.这个算法实现起来很简单 1.百度百科介绍: Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。 许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
932 0
Algorithm:C++语言实现之字符串相关算法(字符串的循环左移、字符串的全排列、带有同个字符的全排列、串匹配问题的BF算法和KMP算法)(二)
Algorithm:C++语言实现之字符串相关算法(字符串的循环左移、字符串的全排列、带有同个字符的全排列、串匹配问题的BF算法和KMP算法)
26 0
数据结构KMP算法配图详解(超详细)
数据结构KMP算法配图详解(超详细)
100 0
二分查找算法
十大算法之二分查找: 二分查找算法是在有序数组中用到的较为频繁的一种算法,在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,其时间为O(n).但二分查找算法则更优,因为其查找时间为O(lgn),譬如数组{1, 2, 3, 4, 5, 6, 7, 8, 9},查找元素6,用二分查找的算法执行的话,其顺序为:     1.第一步查找中间元素,即5,由于56,则6应该在7左边的数组元素中,那么只剩下6,即找到了。
639 0
算法研究之字符串包含
今天看到一道算法题:给定一长一短的俩个字符串A,B,假设A长B短,现在,要你判断B是否包含在字符串A中。 比如,如果是下面两个字符串:  String 1: ABCDEFGHLMNOPQRS  String 2: DCGSRQPOM  答案是true,所有在string2里的字母string1也都有。
623 0
算法研究之左旋字符串
今天看了一个大牛在网上写的关于算法的研究,感触颇深,所以写下跟随其脚步研究的过程。 定义:定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。 如把字符串abcdef左旋转2位得到字符串cdefab。
484 0
+关注
developerguy
A code cleanliness code farmers, A programmer concentrate on elegant design, A want to do with the product architect
1663
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载