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;
}
聊天