字符串的模式匹配之KMP算法

一. 前言

昨天数据结构课上学习了字符串的模式匹配的算法，B-F算法我们已经在博客里提到，具体请查看：字符串的模式匹配之B-F算法但是最后老师还提到了这个KMP算法，并称之为本书的最复杂算法，一听到最复杂便想挑战一下，现将记录如下：

二. KMP算法简介

在计算机科学中，Knuth-Morris-Pratt （克努斯-莫里斯-普拉特）字符串查找算法（常简称为“KMP算法”）可在一个主文本字符串S内查找一个词W的出现位置。此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符————————————摘自维基百科

三. KMP算法实现原理

首先，我们规范一下代词：

T：目标串

P：模式串

j：失配字符的下标

可能有些代词你还看不懂，没有关系，下面用到时候，再回来看就可以了

3.1 通过B-F算法引入KMP

首先我们先来通过B-F算法引出KMP，举例如下：

通过比较我们可以看到，T和P的前四个元素（a,b,c,a）分别对应相等的，但是第五个元素 T4 (b) != P4(f)（我们称之为失配）。按照B-F算法，此时我们应该将P向后移动一位，让T1再与P0相比较，若T1与P0相等，再让T2与P2比较，以此类推……如下图：

我们可以看到，在每次失配的时候，P都是只向后移动一个位置，所以导致B-F算法效率会比较低，那么如何解决这个问题呢？

其实我们可以看到，T和P的前三个元素分别不相等（即a != b != c），但是他们对应相同（即a == a，b == b，c ==c）

所以既然P0 == T0，而T0 != T1，而P1 == T1，所以说P0 != T1 是肯定的，同理，P0也不等于T2，既然我们知道他们不相等，那可以直接跳过这两步，将P向后移动三位，直接让P0和T3对齐开始比较

同时因为我们已经知道T3和P0肯定相等（后面会介绍为啥），所以可以直接从P的下标为1的元素P1和T中失配的元素开始依次比较，这样便取消了回溯。

问题是，我们如才能知道要将P向后移动几位呢？又如何才能知道从P的下标为几的元素开始和T中失配的元素比较呢？

我们先引入前缀和后缀的概念：

3.2 前缀后缀的概念

那么什么是前缀，什么是后缀呢？可以这样理解，拿一个字符串来说

前缀就是以第一个字母开头，但是不以最后一个字母结尾的所有子字符串后缀就是以最后一个字母结尾，但是不以第一个字母开头的所有子字符串，我们以”ABCDABD”为例：

“A”的前缀和后缀都为空集，共有元素的长度为0；

“AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；

“ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

“ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

“ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；

“ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；

“ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

那么我们知道了一个字符串的前缀和后缀的公共元素以及长度，有什么用呢？

拿第3.1节我们举面的例子来说，字符串“abca”的前缀是：a，ab，abc，后缀是：a，ca，bca，公共元素是a，长度为1，在前缀a和后缀a中间的bc这两个元素，，恰好是我们3.1节中提到的P1和P2这两个元素，同时公共元素为1，又恰好从P中的第1个元素开始向后开始和T的失配元素开始比较，所以我们可以总结上面的规律，用来解决3.1节最后提出的两个问题：

3.3 KMP的算法基本原理

当我们知道一个字符串的前缀和后缀的公共元素后

P向右移动的位数为：j- next[j]

P的第几个元素开始和T的失配元素开始比较：从下标为next[j]的开始

看到这里，你一定一脸懵逼，我们知道j是失配的字符的下标，那么next[j]是啥玩意呀？

next[j]其实就是前j个元素的前缀”和”后缀”的最长的共有元素的长度。

还是拿第3.1节我们举面的例子来说，失配字符的下标为j = 4

也就是前四个字符“abca”的前缀是：a，ab，abc，后缀是：a，ca，bca

可以看到，只有a这个元素是前缀和后缀的公共元素，且长度为1，也就是next[4] = 1，那么我们通过j – next[j] = 4 – 1 = 3计算出P需要向右移动的维数，则移动三位，同时因为next[j] = 1，所以从P的第1个元素开始和T中失配元素开始比较。那么我们将P向右移动三位，同时从P的第1个元素P1（b）开始和T中的失配元素T4（b）开始依次比较，这样我们不仅取消了回溯，且只移动了一次就匹配成功。如下图：

这就是KMP算法的基本原理。

四. 如何求next[j+1]的值呢？

我们需要知道P中的每个元素的next[j]的值，才能实现这个算法，我们可以从next[0]开始，依次推出：

以下图为例：已知next[5] = 3，求next[6]

当我们知道next[5] = 3的时候，也就是P0,P1,P2 = P2,P3,P4的时候，说明aba为当前前缀和后缀的最长公共元素

那么next[6]的前缀和后缀的公共元素，最长只能为next[5] + 1 = 4，也就是说我们只需要将第j +1 个元素(下标为j）和下标为next[j] 的元素相比较，查看它们是否相等，便可以验证next[6]的前缀和后缀的公共元素是否为4了。本例中P5 == P3，所以next[6] = 4。

但是如果他们不相等，那么next[6]的前缀和后缀的公共元素的长度只能为 0 < x < next[5] ，x即0，1，2。

总结以上规律如下：
当我们已知next [0~ j]的值，如何求出next [j + 1]的值呢？

若p[ next[j] ] == p[j]，则 next[j + 1 ] = next [j] + 1 = k + 1若p[k ] ≠ p[j]，如果此时p[ next[k] ] == p[j ]，则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[k]，而后重复此过程。相当于在字符p[j+1]之前不存在长度为k+1的前缀”p0 p1, …, pk-1 pk”跟后缀“pj-k pj-k+1, …, pj-1 pj”相等，那么是否可能存在另一个值t+1 < k+1，使得长度更小的前缀 “p0 p1, …, pt-1 pt” 等于长度更小的后缀 “pj-t pj-t+1, …, pj-1 pj” 呢？如果存在，那么这个t+1 便是next[ j+1]的值，此相当于利用已经求得的next 数组（next [0, …, k, …, j]）进行P串前缀跟P串后缀的匹配。

当我们已知next [0~ j]的值，next [j + 1]的值最大为next[j] + 1，最小为0

五. KMP的基本思想

可能看上面的解释，你有些似懂非懂，我们不妨用自然语言再来叙述一遍，来加深你的理解：以下内容引用自逍遥行的知乎回答，已获得本人授权：

甲：abbaabbaaba

在里面寻找

乙：abbaaba

发现第 7 个字符不匹配。

这时候甲把乙叫走了，说你先一边玩去，我自己研究下。

然后甲想，自己已经知道乙的前 6 个字符就是自己的前 6 个字符，不妨先「自己与自己匹配一番」。（这里甲和自己匹配一番，而上面的例子中我们都是把乙和自己匹配一番，其实原理是一样的，因为匹配字符中，甲 = 乙）

然后甲先用 abbaab 这 6 个已知的字符从头开始匹配自己。向右错 1 个位，发现第一个就不一样（不匹配）；向右错 2 个位，还是不匹配。

当错 3 个位的时候，甲发现匹配了一个 a，但是第二个 b 不匹配。

当错 4 个位的时候，匹配了两个。错 5 个位不匹配。后面的东西甲就不知道了，因为他只知道前 6 个字符。

（注：实际的匹配个数是字符串 [0…i] 的后缀与前缀的最长公共长度）

随后，甲把乙叫了过来：

「我已经知道你下一次匹配开始的位置了，来，让你的头部对齐我的第 5 个字符，然后从你的第 3 个字符开始继续匹配我吧！」

关键的地方，在于不要让乙「前功尽弃」——已经匹配了 6 个了，还差一个就结束了，这时不匹配导致从 0 开始，多可惜啊！

现在我告诉你，在不匹配的情况下，你仍然已经匹配了 2 个（乙内心：还好不是 0），并且你可以继续从不匹配的地方开始比较，即用你的 3 个字符与我继续匹配。

那，这个 2 你是怎么算的？

我在你来之前就算好啦！

我先与自己进行匹配（预处理），对每个位置，找「当前位置往前看的最长字符串，它与我的前缀匹配」（当然这个字符串不能是前缀），这个最长字符串的长度，在学术上称作「失配函数」UCCU，从你的第 6 个位置往前看，恰好 [ab] 与你的前缀 [ab] 匹配，但是我的第 7 个字符并不知道你的第 3 个字符是否与我一样，所以你直接从这里开始继续匹配我。以上为 KMP 的基本思想。

六. 代码实现

#include <iostream>
using namespace std;
#include<string.h>
//void GetNext(char* p,int next[])
void GetNext(char* p,int* next)

{
    int pLen = strlen(p);
    next[0] = -1;  ////模版字符串的前缀和后缀的最长公共元素的长度，并初始化第一个元素为-1
    int k = -1;  //k:最大前后缀长度,并初始化为-1，和next[0]对应
    int j = 0;  //j:模版字符串下标
    while (j < pLen - 1)
    {
        //p[k]表示前缀，p[j]表示后缀
        if (k == -1 || p[j] == p[k]) //如果k == -1，说明p[j+1]前缀和后缀没有公共元素,则让next[j] = 0
            //如果p[j] == p[k]，说明p[j+1]前缀和后缀有最长的公共元素，则让next[j] = ++k
        {
            ++k;
            ++j;
            next[j] = k;
        }
        else   //如果k != -1 %=&& p[j] !== p[k],说明需要继续递归前缀索引k = next[k]
        {
            k = next[k];
        }
    }
}

//int KmpSearch(char* s, char* p,int next[])
int KmpSearch(char* s, char* p,int* next)
{
    int i = 0;
    int j = 0;
    int sLen = strlen(s);
    int pLen = strlen(p);
    while (i < sLen && j < pLen)
    {
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
        if (j == -1 || s[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
            //next[j]即为j所对应的next值
            j = next[j];
        }
    }
    if (j == pLen)
        return i - j;
    else
        return -1;
}

int main()
{
    char *s = "abcabcdef";
    char *p = "abcd";
      cout << "sizeof(p) = " << sizeof(p) << endl;
      cout << "sizeof(p) = " << sizeof(p) << endl;
      int *next = new int[sizeof(p)];      //会卡死

    //int *next = new int[strlen(p)]; //不会卡死
    GetNext( p,next);
    cout << KmpSearch(s,p,next);
    return 0;
}