[算法系列之二十六]字符串匹配之KMP算法

  1. 云栖社区>
  2. 博客>
  3. 正文

[算法系列之二十六]字符串匹配之KMP算法

sjf0115 2015-03-01 19:14:00 浏览1120
展开阅读全文

一 简介

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

二 基于部分匹配表的KMP算法

举例来说,有一个字符串”BBC ABCDAB ABCDABCDABDE”,我想知道,里面是否包含搜索串”ABCDABD”?

步骤1:字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索串”ABCDAB D”的第一个字符进行比较。因为字符B与A不匹配,所以搜索串后移一位。

这里写图片描述

步骤2:因为字符B与A不匹配,所以搜索串再往后移一位。

这里写图片描述

步骤3:就这样,直到字符串有一个字符与搜索串的第一个字符相同为止。

这里写图片描述

步骤4:接着比较字符串和搜索串的下一个字符,还是相同。

这里写图片描述

步骤5:直到字符串有一个字符与搜索串对应的字符不相同为止。

这里写图片描述

步骤6:这时,最自然的反应是,将搜索串整体后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把”搜索位置”移到已经比较过的位置,重比一遍。(这就是之前讲的[算法系列之十二]字符串匹配之蛮力匹配

这里写图片描述

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

这里写图片描述

步骤8:怎么做到这一点呢?可以针对搜索串,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

这里写图片描述

步骤9:已知空格与D不匹配时,前面六个字符”ABCDAB”是匹配的。

这里写图片描述

查表可知,最后一个匹配字符B对应的”部分匹配值”为2,因此按照下面的公式算出向后移动的位数:

移动位数 = 已匹配的字符数 - 失配字符的上一位字符对应的部分匹配值

因为 6 - 2 等于4,所以将搜索串向后移动4位,如下图。

这里写图片描述

步骤10:因为空格与C不匹配,搜索串还要继续往后移。这时,已匹配的字符数为2(”AB”),对应的”部分匹配值”为0。所以,移动位数 = 2 - 0,结果为 2,于是将搜索串向后移2位。

这里写图片描述

步骤11:因为空格与A不匹配,继续后移一位。逐位比较,直到发现C与D不匹配。

这里写图片描述

于是,移动位数 = 6 - 2,继续将搜索串向后移动4位。

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

这里写图片描述

如果还要继续搜索(即找出全部匹配),移动位数 = 7 - 0,再将搜索串向后移动7位,这里就不再重复了。

三 部分匹配表(Partial Match Table)

下面介绍《部分匹配表》是如何产生的。首先,要了解两个概念:前缀后缀

  • 前缀指除了最后一个字符以外,一个字符串的全部头部组合;
  • 后缀指除了第一个字符以外,一个字符串的全部尾部组合。

举例说明:
这里写图片描述

部分匹配值就是前缀和后缀的最长的共有元素的长度

以”ABCDABD”为例。

这里写图片描述

由此得到部分匹配表,如下:

这里写图片描述

“部分匹配”的实质是,有时候,字符串头部和尾部会有重复。比如,”ABCDAB”之中有两个AB,那么它的”部分匹配值”就是2(AB的长度)。搜索词移动的时候,第一个AB向后移动4位(字符串长度-部分匹配值),就可以来到第二个AB的位置。

四 基于next数组的KMP算法

通过以上的匹配过程可以看出,问题的关键就是寻找搜索串中最大长度的相同前缀和后缀。找到了搜索串中每个字符之前的前缀和后缀公共部分的最大长度后,便可基于此匹配。而这个最大长度便正是next 数组要表达的含义。

4.1:根据《部分匹配表》求next 数组

经过上面叙述我们已经知道搜索串“ABCDABD”各个前缀后缀的最大公共元素长度了,如下图所示:

这里写图片描述

部分匹配表也由此而出如下所示:

这里写图片描述

有了部分匹配表我们就可以利用下面公式计算移动位数:

移动位数 = 已匹配的字符数 - 失配字符的上一位字符对应的部分匹配值

上文利用部分匹配表和移动位数计算公式进行匹配时,我们发现,当一个字符失配时,其实没必要考虑这个失配的字符,我们每次都是看的是失配字符的上一位字符“部分匹配值”。如此,便引出了next 数组。

这里写图片描述

把next 数组跟“部分匹配表”对比后,不难发现,next 数组相当于“部分匹配表” 整体向右移动一位,然后第一个元素值赋为-1。意识到了这一点,你会惊呼原来next 数组的求解竟然如此简单:就是找最大对称长度的前缀后缀,然后整体右移一位,第一个元素值赋为-1(当然,你也可以直接计算某个字符对应的next值,就是看这个字符之前的字符串中有多大长度的相同前缀后缀)。

更新一下搜索串移动位数的计算公式

移动位数 = 失配字符的位置 - 失配字符next值

其实两公式实质上是一样的,失配字符的位置等于已匹配的字符数,失配字符next 值等于失配字符的上一位字符的部分匹配值,只是换一种说法而已。

4.2 递推求解next数组

对于给定的字符串p,其next数组的含义是:对于k=next[j],p的前缀p[0…k-1]和p的后缀p[j-k…j-1]匹配,k要尽可能的大,且k< j。我们可以根据上述含义写出next的蛮力计算方法。复杂度应该是O(^2)。

换个思路,现在next[0]=-1,next[1]=0。
假设k=next[j],则p[0…k-1]=p[j-k…j-1],那么求next[j+1]有两种情况:

  • 如果p[k] = p[j],则p[0…k]=p[j-k…j],所next[j+1]=k+1=next[j]+1
  • 如果p[k] != p[j],这是可以看做另外一个字符串匹配的问题,主串和模式串都是p,当匹配失败时,k应该如何移动呢?显然是k=next[k]
    void GetNext(string T,int next[]){
        int size = T.size();
        next[0] = -1;
        int k = -1;
        int j = 0;
        while(j < size - 1){
            // p[k]表示前缀,p[j]表示后缀
            if(k == -1 || T[k] == T[j]){
                ++k;
                ++j;
                next[j] = k;
            }//if
            else{
                // 回溯
                k = next[k];
            }
        }//while
    }

引用:

字符串匹配的KMP算法
从头到尾彻底理解KMP
KMP算法求next数组
KMP算法的next[]数组通俗解释

网友评论

登录后评论
0/500
评论
sjf0115
+ 关注