有的时候我们会面临这样的一个问题:有一个文本串s和一个模式串p,我们要在s中找p出现的位置要怎么做呢?

朴素做法

最简单最容易想到的就是暴力匹配。

假设文本串匹配到i位置,模式串匹配到j位置。

  • 若j==len§,则找到,退出即可
  • 若s[i]==p[j],则i++, j++继续匹配下一个字符
  • 若s[i]!=p[j],则i=i-j+1, j=0
bool violentMatch(char *s, char *p)
{
    int slen=strlen(s), plen=strlen(p);
    int i=0, j=0;
    while(i<slen && j<plen)
    {
        if(s[i] == p[j])
            i++, j++;
        else
            i=i-j+1, j=0;
    }
    if(j == plen)
        return true;
    else
        return false;
}

这种暴力做法的时间复杂度为O(n*m)的,n为文本串的长度,m为模式串的长度。

暴力匹配在当前字符匹配失败的时候,只将模式串往后移了一个位置,这样实在是太慢了,能不能一次多移几个位置?

KMP

Knuth-Morris-Pratt算法,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表。

我们先来看看KMP算法的匹配过程吧,看看是怎么跳多几步的。

1

一开始的A与BBC都不匹配,一步一步到第四个的A

2

这时候ABCDAB都匹配上了,但是最后的D和A不匹配,我们能够快速跳到下面的样子

3

观察到上面的AB已经匹配上了,我们是从第2个图直接跳到第3个图的,这就是KMP算法的奇妙之处,我们不需要再一次慢慢匹配前面的AB了,因为我们知道它可以匹配上

这时候C和A匹配不上,我们就跳到下图

4

跳到A和A匹配,这时候匹配上了,继续一个个比较,直到最后一个字母D

5

D又没有匹配上,继续往后跳,变成下图

6

最后成功匹配上了。

多看看几遍KMP算法的匹配过程图,或许能够发现一些奥妙。

前缀函数

KMP算法在失配的时候的“跳”和前缀函数有着密切的关系。

前缀函数的定义:给定一个长度为n的字符串s,前缀函数是一个长度为n的数组。其中π[i]为既是子串[0…i]的前缀同时是这个子串的后缀的最长真前缀长度。一个字符串的真前缀是指其不等于其自身的前缀。根据定义,π[0]=0。

8

所以ABCDABD的前缀函数为[0, 0, 0, 0, 1, 2, 0]

9

next数组

next数组是和前缀函数很类似的东西,next数组也是长度为n的数组。next数组等于前缀函数每个位置往右移一位,再将next[0]设置为-1。

ABCDABD的前缀函数和next数组如下

10

KMP每次的跳都是根据next数组里面的值所决定的。

我们再一次回顾一下KMP算法的匹配过程吧,上面的文本串用s表示,下面的模式串用p表示,且字符串都从0开始编号

1

首先我们一个个匹配A,一开始的BBC都不匹配,直到s[3]的A才和p[0]的A匹配上

这时候一位位匹配,直到p[6]与s[9]失配

2

这时候我们查next数组所对应失配位的值,即next[6]的值,为2,我们将模式串的指针j(这时候j为6)变为next[j],即j=2。也就是我们下一次比较的是p[2]和s[9],即跳到下图的样子

3

这时候我们发现p[2]和s[9]失配了,我们查next数组,发现next[2]=0,所有将模式串的指针j变为0,下一次用p[0]和s[9]匹配。

4

这时候p[0]和s[9]匹配上了,后面慢慢的匹配,直到p[6]和s[15]失配了

5

我们查next数组,next[6]=2,将模式串的指针j变为2,下一次匹配p[2]和s[15]

发现p[2]和s[15]匹配上了,我们就一位位往后匹配,发现最后成功匹配上了所有的字符

6

成功!

先不管next数组是如何求来的,多看几次图示的匹配过程,体会每次失配时,next数组是如何帮助我们“跳”的。

这个“跳”就和上面讲的前缀函数密切相关了,π[i]就是子串s[0…i]的最长的共同前后缀的长度。

比如ABCDABD这一个模式串,我们在D失配的时候,观察D前面的串ABCDAB,发现这个串的最长公共前缀后缀为AB,我们在匹配到D的时候才失配,说明前面的ABCDAB都和文本串匹配上了,所以我们可以将前缀AB挪到后缀AB的位置,可以知道这个时候前缀AB和文本串是匹配的,所以我们的模式串直接从C开始下一次的匹配,即模式串的指针j变为next[j],还记得next[6]为多少吗?对!next[6]=2,我们的j变为了2,刚好是p[2]我们想要的C的位置(字符串从0开始编号)

不知道到这里能否明白next的妙用了?但是神奇的next数组如何求呢?

next的求解

我们利用next数组在文本串中寻找模式串p,即文本串和模式串匹配。求解next数组的时候就像是模式串和模式串匹配。

假设我们求出了next[0…j],如何求解next[j+1]呢?

设k为next[j]

  • 若p[k]==p[j+1],则next[j+1] = next[j]+1 = k+1
  • 若p[k]!=p[j+1],则令k=next[k],一直递归这个过程。这个过程相当于,在p[j+1]之前不存在一个长度为k+1的前缀"p0, p1, p2, … ,pk"和长度为k+1的后缀"Pj-k, pj-k+1, pj-k+2, …, pj+1"相等,所以我门令k=next[k]继续往前找,直到找到一个更短的前缀使得也是子串p[0…j+1]的后缀。如果实在没有的话,则next[j+1]=0

这个过程很抽象,很难理解,我们先看看代码吧。

int nxt[maxn];
void getNext(char *p)
{
    int plen=strlen(p);
    int k=-1, j=0;
    nxt[0]=-1;
    while(j<plen)
    {
        if(k==-1 || p[k]==p[j])
        {
            j++, k++;
            nxt[j] = k;
        }
        else
        {
            k = nxt[k];
        }
    }
}

可能看到这更懵了,k=nxt[k]???可能看了下面这个图能稍微理解这一步。

7

勘误:图上的两个虚线括号不包括Pk和Pj

若p[j]==p[k],则next[j+1]就为k+1。若p[j]!=p[k],则让k=next[k],第一个蓝色块和第四个蓝色块是匹配上的,只需判断两个绿色的块是否相同即可,类似一种递归的过程。

四个蓝色块画的大小不太一样,但是它们所代表的子字符串都是相同的。

KMP模板

请确保真的理解了next数组的含义及求解!!!

int nxt[maxn];
char s[maxn], p[maxn];

void getNext(char *p)
{
    int len=strlen(p);
    int j=0, k=-1, nxt[0]=-1;
    while(j<len)
    {
        if(k==-1 || p[j]==p[k])
            nxt[++j] = ++k;
        else
            k=nxt[k];
    }
}

// 返回模式串p在s中首次出现的位置
int kmp(char *s, char *p)
{
    int i=0, j=0;
    int slen=strlen(s), plen=strlen(p);
    getNext(p);
    while(i<slen && j<plen)
    {
        if(j==-1 || s[i]==p[j])
            i++, j++;
        eles
            j=nxt[j];
    }
    if(j==plen)
        return i-plen;
    else
        return -1;
}

// 返回模式串p在s中出现的次数
int kmp(char *s, char *p)
{
    int ans=0, i=0, j=0;
    int slen=strlen(s), plen=strlen(p);
    getNext(p);
    for(i=0; i<slen; i++)
    {
        while(j>0 && s[i]!=p[j])
            j=nxt[j];
        if(s[i]==p[j])
            j++;
        if(j==plen)
        {
            ans++;
            j=0;
        }
    }
    return 0;
}