删除文章

确定要删除这篇文章吗?

取消
确定

KMP算法

     阅读(416)  2017-10-24 20:07:12

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。


//  求子串nextval[]数组
//  如:  
//  元素编号       0    1    2    3    4    5    6    7
//  子串           a    b    a    a    b    c    a    c
//  next值        -1    0    0    1    1    2    0    1
//  nextval值     -1    0    -1   1    0    2    -1   1
//
//  求next值,根据前一位(假如其字符为x)求后一位,如果字符x与其next值对应的字符相等则后一位在前一位的基础上加1。
//  如果不相等就根据next值继续往前找直到找到与字符x相等为止,那么就在找到的字符对应的next值基础上加1。
//  如果找到了next值为-1处还没找到,它的next值就为0.
//  步骤如下:
//  1>第0位必为-1;
//  2>第1位必为0;
//  3>第2位,前一位为b,next值为0,查看next值对应的字符为a,与它不相等所以为0;
//  4>第3位,前一位为a,next值为0,查看next值对应的字符为a,与它相等所以1;
//  5>第4位,前一位为a,next值为1,查看next值对应的字符为b,与它不相等,根据b的next值0继续往前找,找到了a与它相等,
//    所以在b next值的基础上加1,即为1;
//  6>第5位,前一位为b,next值为1,查看next值对应的字符为b,与它相等所以在b next值的基础上加1等于2;
//  7>第6位,前一位为c,next值为2,查看next值对应的字符为a,与它不相等,继续查看a的next值0,编号0对应的字符为a还是不等,
//    同时已到达-1的位置所以为0;
//  8>第7位,前一位为a,next值为0,查看next值对应的字符为a,与它相等所以为1。
//
//  根据next值求nextval值,当前字符与其next值对应的字符进行比较,不相等则为next值,相等则为next值字符对应的next值。
//  1>第0位必为-1;
//  2>第1位字符为b,next值为0,与其next值对应的字符为a,不相等,为0;
//  3>第2位字符为a,next值为0,与其next值对应的字符为a,相等,为-1;
//  4>第3位字符为a,next值为1,与其next值对应的字符为b,不相等,为1;
//  5>第4位字符为b,next值为1,与其next值对应的字符为b,相等,为0;
//  6>第5位字符为c,next值为2,与其next值对应的字符为a,不相等,为2;
//  7>第6位字符为a,next值为0,与其next值对应的字符为a,相等,为-1;
//  8>第7位字符为c,next值为1,与其next值对应的字符为b,不相等,为1。

#include <assert.h>
#include <iostream>
using namespace std;

void GetNextValue(const char *str, int * const next_value)
{
    assert(str != NULL && next_value != NULL);

    int i = 0;
    int j = -1;
    int len = (int)strlen(str);

    next_value[i] = -1;

    while (i < len - 1)
    {
        if (j == -1 || str[i] == str[j])
        {
            ++i;
            ++j;
            if (str[i] != str[j])
            {
                next_value[i] = j;
            }
            else
            {
                next_value[i] = next_value[j];
            }
        }
        else
        {
            j = next_value[j];
        }
    }
}

// KMP算法求子串在父串里出现的位置(由0开始)
int KmpSearch(const char *src, const char *dest, const int *next_value)
{
    assert(src != NULL && dest != NULL && next_value != NULL);

    int i = 0;
    int j = 0;
    int src_len = (int)strlen(src);
    int dest_len = (int)strlen(dest);

    while (i < src_len && j < dest_len)
    {
        if (j == -1 || src[i] == dest[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next_value[j];
        }
    }

    if (j >= dest_len)
    {
        return i - dest_len;
    }
    else
    {
        return -1;
    }
}

int _tmain(int argc, char *argv[])
{
    char src[] = "acabaabaabcacaabc";
    char dest[] = "abaabcac";

    const int count = sizeof(dest) / sizeof(dest[0]) - 1;
    int next_value[count] = {0};

    GetNextValue(dest, next_value);

    int find_pos = KmpSearch(src, dest, next_value);
    
    cout << "find pos = " << find_pos << endl;
    
    cin.get();
    return 0;
}


文章评论

Keep it simple,stupid
文章数
300
总访问量
443105
今日访问
994
最近评论

xuehaoyun : 很不错,来围观一下
tujiaw : 抱歉csdn code服务关闭了,这个代码我也找不到了
于淞 : 你好,这个文章的源码能分享一下吗,songsong9181@163.com,谢谢了 上面的写错了
于淞 : 你好,这个文章的源码能分享一下吗,838106303@163.com,谢谢了 上面的链接不能用了
tujiaw : 多谢多谢
essaypinglun college-paper.org : 很好的博客,赞赞
Folly : 这个实现有点奇怪,Qt为什么没有统一的比对方法。
过多s : alert("hello, world!")
tujiaw : 还不错哦
回到顶部