KMP(字符串匹配)

时间:2021-11-02 12:03:09

1、KMP是一种用来进行字符串匹配的算法,首先我们来看一下普通的匹配算法:


现在我们要在字符串ababcabcacbab中找abcac是不是存在,那么传统的查找方法就是一个个的匹配了,如图:

KMP(字符串匹配)

经过六趟匹配之后,终于匹配上了。现在是数据比较小的时候,大家可能没有什么感觉,如果我们的数据是百万级别的,那用这种方法无疑复杂度太高了,很难接受。

2、模式匹配的一种改进算法:


这种改进算法由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的,因此人们称他为克努特-莫里斯-普拉特操作(简称KMP算法)。此算法可以在O(n + m)的时间数量级上完成串的模式匹配操作。其改进在于:每当一趟匹配过程中出现字符比较不等时,不需要回溯i指针,而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后,继续进行比较。下面先从具体的例子看起。

KMP(字符串匹配)

回顾上面的传统的匹配过程,在第三趟的匹配中,当i = 7、j = 5字符比较不等时,又从i = 4、j = 1重新开始比较。然后,经仔细观察发现,在i = 4和j = 1,i = 5和j = 1以及i = 6和j = 1这3次比较都是不必进行的。因为从第三趟部分比配结果就可得出,主串中第4、5和6个字符必然是'b'、'c'和'a'(即模式串中的第2、3、和4个字符)。因为模式中的第一个字符是a,因此它无需再和这3个字符进行比较,而仅需要将模式串向右滑动3个字符的位置继续进行i = 7、j = 2时字符比较即可。同理,在第一趟匹配中出现字符不等时,仅需要将模式向右移动两个字符的位置继续进行i = 3、j = 1时的字符比较。由此,在整个匹配过程中,i指针没有回溯,如图4.4所示。

3、KMP


此时我们构建一个next[]数组,这个数组的意思就是,当主串中的第i个字符与模式串中的第j个字符失配时,模式串中的next[j]个字符与第i个字符继续进行比较,显然复杂度提高了很多。

KMP(字符串匹配)KMP(字符串匹配)

匹配代码:

int index_KMP()

{

    int stra = strlen(a);

    int strb = strlen(b);

    int i = -,j = -;

    while(i < stra && j < strb)

    {

        if(j == - || a[i] == b[j])

        {

            i++;j++;

        }

        else

        {

            j = next[j];

        }

    }

    if(j >= strb)

    {//在a中找到了b字符串

        return ;

    }

    return ;

}

4、求next数组:


KMP算法实在已知模式串的next函数值的基础上执行的,那么,如何求得模式串的next函数值呢?

从上述讨论可见,此函数值仅取决于模式串本身和相匹配的主串无关。我们可从分析其定义出发用地推的方法求得next函数值。

设next[j] = k,这表明在模式串中存在下列关系:'p1....pk-1' = 'pj-k+1....pj-1'。其中k为满足1 < k < j的某个值,此时的next[j + 1] = ?可能有两种情况:

(1)若pk = pj,则表明模式串中'p1....pk' = 'pj-k+1....pj'

这就是说next[j+1] = k+1,即next[j + 1] = next[j] + 1。

(2)若pk != pj,则表明在模式串中‘p1....pk’ != 'pj-k+1....pj'

此时可把求next函数值的问题看成是一个模式匹配的问题,整个模式串既是主串又是模式串,而当前在匹配过程中,已有pj-k+1=p1,pj-k+2=p2,...,pj-1=pk-1,则当pj!=pk时应将模式向右滑动至模式中的第next[k]个字符和主串的第j个字符相比较。若next[k] = k',且pj = pk',则说明在主串中的第j+1个字符之前存在一个长度为k’(即next[k])的最长子串,和模式串中从首字符起长度为k'的子串相等,即'p1...pk'' = 'pj-k+1...pj'   (1 < k' < k < j)      (4 - 10)

这就是说next[j + 1] = k' + 1即next[j + 1] = next[k] + 1。

同理,若pj!=pk',则将模式继续向右滑动直至将模式中第next[k']个字符和pj对齐,....,依次类推,直至pj和模式中某个字符匹配成功或者不存在任何k'(1 < k' < j)满足等式(4 - 10) 则next[j + 1] = 0。

代码:

void get_next()

{

    next[] = -;

    int j = -;

    int i = ;

    int str = strlen(b);

    while(i < str - )

    {

        if(j == - || b[i] == b[j])

        {

            next[++i] = ++j;

        }

        else

        {

            j = next[j];

        }

    }

}

5、给出一份完整代码:


#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

char a[];

char b[];

int next[];

void get_next()

{

    next[] = -;

    int j = -;

    int i = ;

    int str = strlen(b);

    while(i < str - )

    {

        if(j == - || b[i] == b[j])

        {

            next[++i] = ++j;

        }

        else

        {

            j = next[j];

        }

    }

}

int index_KMP()

{

    int stra = strlen(a);

    int strb = strlen(b);

    int i = -,j = -;

    while(i < stra && j < strb)

    {

        if(j == - || a[i] == b[j])

        {

            i++;j++;

        }

        else

        {

            j = next[j];

        }

    }

    if(j >= strb)

    {//在a中找到了b字符串

        return ;

    }

    return ;

}

int main()

{

    while(scanf("%s%s",a,b)!=EOF)

    {

        get_next();

        if(index_KMP())

        {

            printf("YES\n");

        }

        else

        {

            printf("NO\n");

        }

    }

    return ;

}

运行结果:

KMP(字符串匹配)