KMP

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

朴素做法

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

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

• 若j==len(p)，则找到，退出即可
• 若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算法的匹配过程吧，看看是怎么跳多几步的。

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

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

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

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

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

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

最后成功匹配上了。

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

前缀函数

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

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

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

next数组

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

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

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

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

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

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

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

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

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

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

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

成功！

先不管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]？？？可能看了下面这个图能稍微理解这一步。

若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;
}