MENU

KMP算法

April 2, 2018 • 文章

一:背景

给定一个主串(以 S 代替)和模式串(以 P 代替),要求找出 P 在 S 中出现的位置,此即串的模式匹配问题。

Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。

在继续下面的内容之前,有必要在这里介绍下两个概念:真前缀真后缀

由上图所得, "真前缀"指除了自身以外,一个字符串的全部头部组合;"真后缀"指除了自身以外,一个字符串的全部尾部组合。(网上很多博客,应该说是几乎所有的博客,也包括我以前写的,都是“前缀”。严格来说,“真前缀”和“前缀”是不同的,既然不同,还是不要混为一谈的好!)

二:朴素字符串匹配算法

初遇串的模式匹配问题,我们脑海中的第一反应,就是朴素字符串匹配(即所谓的暴力匹配),代码如下:

/* 字符串下标始于 0 */
int NaiveStringSearch(string S, string P)
{
    int i = 0;    // S 的下标
    int j = 0;    // P 的下标
    int s_len = S.size();
    int p_len = P.size();

    while (i < s_len && j < p_len)
    {
        if (S[i] == P[j])  // 若相等,都前进一步
        {
            i++;
            j++;
        }
        else               // 不相等
        {
            i = i - j + 1;
            j = 0;
        }
    }

    if (j == p_len)        // 匹配成功
        return i - j;

    return -1;
}

暴力匹配的时间复杂度为 $O(nm)$,其中 $n$ 为 S 的长度,$m$ 为 P 的长度。很明显,这样的时间复杂度很难满足我们的需求。

接下来进入正题:时间复杂度为 $Θ(n+m)$ 的 KMP 算法。

三:KMP字符串匹配算法

3.1 算法流程

以下摘自阮一峰的字符串匹配的KMP算法,并作稍微修改。

(1)

首先,主串"BBC ABCDAB ABCDABCDABDE"的第一个字符与模式串"ABCDABD"的第一个字符,进行比较。因为B与A不匹配,所以模式串后移一位。

(2)

因为B与A又不匹配,模式串再往后移。

(3)

就这样,直到主串有一个字符,与模式串的第一个字符相同为止。

(4)

接着比较主串和模式串的下一个字符,还是相同。

(5)

直到主串有一个字符,与模式串对应的字符不相同为止。

(6)

这时,最自然的反应是,将模式串整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。

(7)

一个基本事实是,当空格与D不匹配时,你其实是已经知道前面六个字符是"ABCDAB"。KMP算法的想法是,设法利用这个已知信息,不要把"搜索位置"移回已经比较过的位置,而是继续把它向后移,这样就提高了效率。

(8)

i01234567
模式串ABCDABD'\0'
next[i]-10000120

怎么做到这一点呢?可以针对模式串,设置一个跳转数组int next[],这个数组是怎么计算出来的,后面再介绍,这里只要会用就可以了。

(9)

已知空格与D不匹配时,前面六个字符"ABCDAB"是匹配的。根据跳转数组可知,不匹配处D的next值为2,因此接下来从模式串下标为2的位置开始匹配

(10)

因为空格与C不匹配,C处的next值为0,因此接下来模式串从下标为0处开始匹配。

(11)

因为空格与A不匹配,此处next值为-1,表示模式串的第一个字符就不匹配,那么直接往后移一位。

(12)

逐位比较,直到发现C与D不匹配。于是,下一步从下标为2的地方开始匹配。

(13)

逐位比较,直到模式串的最后一位,发现完全匹配,于是搜索完成。

3.2 next数组是如何求出的

next数组的求解基于“真前缀”和“真后缀”,即next[i]等于P[0]...P[i - 1]最长的相同真前后缀的长度(请暂时忽视i等于0时的情况,下面会有解释)。我们依旧以上述的表格为例,为了方便阅读,我复制在下方了。

i01234567
模式串ABCDABD'\0'
next[ i ]-10000120
  1. i = 0,对于模式串的首字符,我们统一为next[0] = -1
  2. i = 1,前面的字符串为A,其最长相同真前后缀长度为0,即next[1] = 0
  3. i = 2,前面的字符串为AB,其最长相同真前后缀长度为0,即next[2] = 0
  4. i = 3,前面的字符串为ABC,其最长相同真前后缀长度为0,即next[3] = 0
  5. i = 4,前面的字符串为ABCD,其最长相同真前后缀长度为0,即next[4] = 0
  6. i = 5,前面的字符串为ABCDA,其最长相同真前后缀为A,即next[5] = 1
  7. i = 6,前面的字符串为ABCDAB,其最长相同真前后缀为AB,即next[6] = 2
  8. i = 7,前面的字符串为ABCDABD,其最长相同真前后缀长度为0,即next[7] = 0

那么,为什么根据最长相同真前后缀的长度就可以实现在不匹配情况下的跳转呢?举个代表性的例子:假如i = 6时不匹配,此时我们是知道其位置前的字符串为ABCDAB,仔细观察这个字符串,首尾都有一个AB,既然在i = 6处的D不匹配,我们为何不直接把i = 2处的C拿过来继续比较呢,因为都有一个AB啊,而这个AB就是ABCDAB的最长相同真前后缀,其长度2正好是跳转的下标位置。

有的读者可能存在疑问,若在i = 5时匹配失败,按照我讲解的思路,此时应该把i = 1处的字符拿过来继续比较,但是这两个位置的字符是一样的啊,都是B,既然一样,拿过来比较不就是无用功了么?其实不是我讲解的有问题,也不是这个算法有问题,而是这个算法还未优化,关于这个问题在下面会详细说明,不过建议读者不要在这里纠结,跳过这个,下面你自然会恍然大悟。

思路如此简单,接下来就是代码实现了,如下:

/* P 为模式串,下标从 0 开始 */
void GetNext(string P, int next[])
{
    int p_len = P.size();
    int i = 0;   // P 的下标
    int j = -1;  
    next[0] = -1;

    while (i < p_len - 1)
    {
        if (j == -1 || P[i] == P[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

一脸懵逼,是不是。。。上述代码就是用来求解模式串中每个位置的next[]值。

下面具体分析,我把代码分为两部分来讲:

(1):i和j的作用是什么?

i和j就像是两个”指针“,一前一后,通过移动它们来找到最长的相同真前后缀。

(2):if...else...语句里做了什么?

假设i和j的位置如上图,由next[i] = j得,也就是对于位置i来说,区段[0, i - 1]的最长相同真前后缀分别是[0, j - 1]和[i - j, i - 1],即这两区段内容相同

按照算法流程,if (P[i] == P[j]),则i++; j++; next[i] = j;;若不等,则j = next[j],见下图:

next[j]代表[0, j - 1]区段中最长相同真前后缀的长度。如图,用左侧两个椭圆来表示这个最长相同真前后缀,即这两个椭圆代表的区段内容相同;同理,右侧也有相同的两个椭圆。所以else语句就是利用第一个椭圆和第四个椭圆内容相同来加快得到[0, i - 1]区段的相同真前后缀的长度。

细心的朋友会问if语句中j == -1存在的意义是何?第一,程序刚运行时,j是被初始为-1,直接进行P[i] == P[j]判断无疑会边界溢出;第二,else语句中j = next[j],j是不断后退的,若j在后退中被赋值为-1(也就是j = next[0]),在P[i] == P[j]判断也会边界溢出。综上两点,其意义就是为了特殊边界判断。

四:完整代码

#include <iostream>
#include <string>

using namespace std;

/* P 为模式串,下标从 0 开始 */
void GetNext(string P, int next[])
{
    int p_len = P.size();
    int i = 0;   // P 的下标
    int j = -1;  
    next[0] = -1;

    while (i < p_len - 1)
    {
        if (j == -1 || P[i] == P[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

/* 在 S 中找到 P 第一次出现的位置 */
int KMP(string S, string P, int next[])
{
    GetNext(P, next);

    int i = 0;  // S 的下标
    int j = 0;  // P 的下标
    int s_len = S.size();
    int p_len = P.size();

    while (i < s_len && j < p_len)
    {
        if (j == -1 || S[i] == P[j])  // P 的第一个字符不匹配或 S[i] == P[j]
        {
            i++;
            j++;
        }
        else
            j = next[j];  // 当前字符匹配失败,进行跳转
    }

    if (j == p_len)  // 匹配成功
        return i - j;
    
    return -1;
}

int main()
{
    int next[100] = { 0 };

    cout << KMP("bbc abcdab abcdabcdabde", "abcdabd", next) << endl; // 15
    
    return 0;
}

五:KMP优化

i01234567
模式串ABCDABD'\0'
next[ i ]-10000120

以3.2的表格为例(已复制在上方),若在i = 5时匹配失败,按照3.2的代码,此时应该把i = 1处的字符拿过来继续比较,但是这两个位置的字符是一样的,都是B,既然一样,拿过来比较不就是无用功了么?这我在3.2已经解释过,之所以会这样是因为KMP不够完美。那怎么改写代码就可以解决这个问题呢?很简单。

/* P 为模式串,下标从 0 开始 */
void GetNextval(string P, int nextval[])
{
    int p_len = P.size();
    int i = 0;   // P 的下标
    int j = -1;  
    nextval[0] = -1;

    while (i < p_len - 1)
    {
        if (j == -1 || P[i] == P[j])
        {
            i++;
            j++;
          
            if (P[i] != P[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];  // 既然相同就继续往前找真前缀
        }
        else
            j = nextval[j];
    }
}

六:参考文献

Archives QR Code Tip
QR Code for this page
Tipping QR Code
Leave a Comment

已有 13 条评论
  1. 以后做算法的时候 用什么语言去实现其实都没有关系

    但是要完全在算法层面去描述算法 剔除语言的特点

    你在分析的过程中使用了c 故而会考虑 '\0’

    导致你的算法会考虑这个事情

    故而有while循环数组越界的问题

    比如说在Java中去实现 里面的条件得是 i < len - 1

    也就是说代码移植到其他语言上还是有问题 因为‘\0’不应该出现在算法的考虑过程中

    1. @youyinnn
      嗯,你说的对,这点确实需要注意,谢谢你的提醒。@(真棒)

  2. 无所谓长久 无所谓长久

    在KMP函数中,那个if的判断j应该是==0吧,不应该是==-1吧。==-1我运行是死循环

    1. @无所谓长久
      你用的什么数据出现死循环的?主串和模式串分别说下,我这边测试下。

  3. 前面网址打错了,多发一遍。
    有个疑问: 在优化版本中,求 nextval[i+1] 时,要求 P[i+1] != P[j+1],然后把 j+1 赋值给 nextval[i+1]。然后就疑问就产生了: 根据这个逻辑,那么P[i] != P[j] 应该是满足的(因为前面求 nextval[i] 的时候会进行判断),这样 if 判断条件的 P[i] == P[j] 是否显得多余?

    1. @铁头的头很铁
      你可能还没理解,可以再读几遍文章@(乖)

  4. 首先谢谢博主分享。
    有个疑问: 在优化版本中,求nextval[i+1] 时,要求P[i+1] != P[j+1],然后把j+1赋值给nextval[i+1]。然后就疑问就产生了:根据这个逻辑,那么
    P[i] != P[j]应该是满足的(因为前面求nextval[i]的时候会进行判断),这样if判断条件的P[i] == P[j]是否显得多余?

  5. 这里遇到这样一个问题,验证”ababaaababaa“的next序列。
    a b a b a a a b a b a a
    0 1 2 3 4 5 6 7 8 9 10 11

    next 0 = -1; 前面没有序列,人为规定
    next 1 = 0; 前面的序列为a,真前后缀都没有,next 1为0
    next 2 = 0; 前面的序列为ab,前缀:a 后缀:b,所以next 2为0
    next 3 = 1; 前面的序列为aba,前缀:a 、ab 后缀:a 、 ba,所以next 3为1
    next 4 = 1; 前面的序列为abab,前缀:a 、ab、aba 后缀:b、ab、bab,所以next 4为1
    next 5 = 2; 前面的序列为ababa,前缀:a 、ab、aba、abab 后缀:a 、 ba、aba、baba,所以next 5为2
    next 6 = 1; 前面的序列为ababaa,前缀:a 、ab、aba、abab、ababa 后缀:a 、 aa、baa、abaa、babaa,所以next 6为1
    ......

    算到next 6心想已经很长了,不想用这个方法算了,干脆用博主的代码把这个next序列生成一下!这里好像不能贴图,把结果贴上来。
    a b a b a a a b a b a a
    0 1 2 3 4 5 6 7 8 9 10 11
    代码结果:-1 0 0 1 2 3 1 1 2 3 4 5
    手算结果:-1 0 0 1 1 2 1 .......

    博主能看一下我人工算的有没有问题吗?眼睛已经花了!

    1. @林枫
      是你算错了,我的代码没问题,你对比下在哪个位置错了,然后再去看下真前后缀长度。

  6. Ni Hao Ni Hao

    while循环求next数组的条件应该是i < p_len - 1,不然数组会越界。

    1. @Ni Hao
      不会越界,此时正好落在结束字符'\0'上,而且这个位置的next值你仔细观察,会发现它很有趣的。

    2. jcd jcd

      @刘毅
      首先感谢博主的文章让我受益匪浅,但之所以博主的代码能得出某些正确的结果是因为next数组没有取实际的大小,next数组多算了一些错误的数,但由于测试用例的长度太小用不到那些错误的数,所以能得出某些正确的结果,我参考其他的资料也应该是 next 数组的条件应该是 i < p_len - 1,我实际测试过,每次先输出数组要使用的下标,确实越界了,但是程序不报越界异常。举个例子ABABABB,手动算一下就知道不对了。

    3. @jcd
      首先 i < p_len 并没有错,它只是多算了一步,就是next[p_len]这个值,它代表整个完整的模式串的最长真前后缀。

      确实,在模式匹配中,这个位置的值永远不会用到,但是这个值,我上面的评论已经说过,它在某些情况下非常有用,具体如何,请去online judge寻找相关 KMP 试题。