KMP算法学习笔记

前言

什么是KMP算法？

KMP算法（以三位发明者的名字命名）是一种字符串匹配算法，它能在主串（目标串）中找到模式串首次出现的位置。你在文本编辑器中进行全文搜索时，就是在做这个操作。惊人的是，该算法的时间复杂度为O(m+n)，这是一个线性复杂度的算法！（其中m、n分别为目标串和模式串的长度）

O(m*n)的暴力解法显而易见，而我们的第一反应可能是最终答案应该是个O(mlogn)或者O(nlogm)之类的解法，但这个O(m+n)……实在是过于惊人了。线性的时间复杂度意味着目标串和模式串都只能被不回溯的遍历，或是只被回溯有限多次。

这究竟如何成为可能？

让我们先来看看这个巧妙的算法：

int kmp(string s1, string s2)
{
    int* next = new int[s2.size()];
    getnext(s2, next);
    int i = 0, j = 0;
    while (i<int(s1.size()) && j<int(s2.size()))
    {
        if (j == -1 || s1[i] == s2[j])
        {
            i++; j++;
        }
        else
        {
            j = next[j];
        }
    }
    if (j == s2.size())
    {
        delete[]next;
        next = nullptr;
        return i - s2.size();
    }
    else
    {
        delete[]next;
        next = nullptr;
        return -1;
    }
}

//取得模式串的next[]
void getnext(string s2, int next[])
{
    unsigned int j = 0;
    int k = -1;
    next[j] = k;
    while (j < s2.size() - 1)
    {
        if (k == -1 || s2[j] == s2[k])
        {
            j++; k++;
            if (s2[j] == s2[k])
            {
                next[j] = next[k];
            }
            else
            {
                next[j] = k;
            }
        }
        else
        {
            k = next[k];
        }
    }
}

看起来倒是不太复杂，可是为什么可以这样算呢？接下来我们将会一步一步展示KMP算法。

从暴力解法出发

容易想到，我们要找的其实是子串在主串中的起始位置，而这个起始位置顶多只有m-n个（主串中最后那一小段必不可能，因为它后面一共也没有n个字符了）。我们只要列举这m-n个起始位置，之后对后面的n个位置一一匹配就可以了嘛！

这肯定是可行的：

int substr(string s, string p) {
    int m = s.size(), n = p.size();
    for (int i = 0; i <= m - n; i++)
    {
        int j = i, k = 0;
        while (k < n && s[j] == p[k])
        {
            j++;
            k++;
        }
        if (k == m) 
            return i;
    }
    return -1;
}

仔细一看，喜提O(m*n)……

我们注意到，这里出现了指向主串的指针j和指向模式串的指针k。

每次s[j]和p[k]匹配成功，则j、k各加一；（当前这个字符匹配上了，要匹配下一个）
每次s[j]和p[k]不匹配，则j、k需要回退，j回退到++i处，k回退到0

这些回退真的都是必要的吗？如果我们要达到线性时间复杂度，就必须克服这些回退。主串通常会远比模式串长。至少，指向主串的指针一步都不能退！

如何优化？

让我们来举例说明一下，何种回退是不必要的：

主串	A	B	C	A	B	A	B	C	D
模式串	A	B	A	B	C

当前指向主串和模式串的指针位于（0,0）处。我们继续移动指针直到遇到不匹配（粗体表示已匹配的部分）：

主串	A	B	C	A	B	C	D	A	D
子串	A	B	A	B	C

第3个字符匹配失败了。如果按之前的暴力解法，我们需要从B开始继续：

主串	A	B	C	A	B	C	D	A	D
模式串		A	B	A	B	C

但这有点低效了。我们不需要回退主串，单凭模式串的信息就足以知道，第3个字符匹配失败时，不仅仅意味着以第1个字符为起始的子串不能成功匹配，第2个字符为起始的子串同样不能。因为该位置已经匹配上B了，那就不可能是A。而我们这里还要试图去检查主串中以第2个字符为起始的子串是否能匹配上，这是多余的……因此主串无需回退到第2个字符（B）的位置去，而是让主串和子串的指针同时+1。

另外，我们考虑另一种可能：

主串	A	B	A	B	A	B	C
模式串	A	B	A	B	C

这时候我们已经知道主串中从位置0开始的子串（“ABABA”）不能匹配了，但失配发生在位置4（第五个字符）。我们仅凭模式串的信息就足以知道，若第五个字符失配，那么以位置1、位置3开头的子串都不可能匹配，但以位置2（第三个字符）开头的子串是可能匹配的。因为当前位置模式串失配的字符C前面的这一小段字符（AB）刚好等于模式串自身开头的一小段字符！

所以，我们可以主串指针不动、子串指针回退：

主串	A	B	A	B	A	B	C
模式串			A	B	A	B	C

至此，KMP算法的主要思路就出来了：指向主串的指针始终不进行回退，当发生不匹配时，要么回退模式串指针、要么主串指针单方面前进；而是否回退模式串指针、回退到什么地方，只需要知道模式串本身和当前指向模式串的哪里就够了！

我们使用next数组来记录当发生不匹配时，子串指针应该回退到哪里。这就得到了KMP算法：

int kmp(string s1, string s2)
{
    int* next = new int[s2.size()];
    getnext(s2, next);
    int i = 0, j = 0;
    while (i<int(s1.size()) && j<int(s2.size()))
    {
        if (j == -1 || s1[i] == s2[j])
        {
            i++; j++;
        }
        else
        {
            j = next[j];
        }
    }
	// 下面是判断结果以及手动释放内存，核心逻辑只有上面这段
    if (j == s2.size())
    {
        delete[]next;
        next = nullptr;
        return i - s2.size();
    }
    else
    {
        delete[]next;
        next = nullptr;
        return -1;
    }
}

next[]的求法

注意！KMP算法最关键的地方就在这里了！

next[j]=k的意义是“当模式串位于[j]的字符无法与主串当前的字符相匹配时，模式串应该回退到k处。这是由于模式串中从0到k的这一段刚好和模式串中从j-k到j的这一段是一样的。”。

显然，如果连模式串第一个值都无法与主串当前的字符匹配，那么主串当前的字符肯定不是我们要的，需要让主串指针+1了。令next[0]=-1。

next[]的其他值按以下步骤递推而来：

若模式串s中下标为j的元素对应的next[j]为k，且s[j]=s[k]，那么令next[j+1]=k+1。（这是因为，next[j]=k意味着s最开头0~k-1的元素与位于j前面的j-k~j-1元素一一相等，所以可以从k开始比较。如果s[j]=s[k]，意味着位于0~k的元素与位于j-k~j的元素相等，也就是next[j+1]=k+1）

若s[j]不等于s[k]，令k=next[k]。（如果j-k~j-1无法与最前面的k+1个元素匹配，也就是说我们没办法找到最长的这个串了。但是我们可以找到次长的。k肯定比j小，所以next[k]已经计算出来了。这里一边计算后面的结果一边利用前面的结果。）

//取得模式串的next[]
void getnext(string s2, int next[])
{
    unsigned int j = 0;
    int k = -1;
    next[j] = k;
    while (j < s2.size() - 1)
    {
        if (k == -1 || s2[j] == s2[k])
        {
            j++; k++;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}

不难看出getnext的过程和使用next的过程十分相似。当我们求解next[j]时，由于j前面部分的next已经被算出来了，我们实际上是在用模式串自身在匹配自身。

等等……你之前说过O(m+n)……

乍一看不容易看出来这个算法是O(m+n)的，毕竟主串虽然不回退，子串还是回退的。那么让我们来仔细地分析一下：

对于kmp(s1,s2)，我们每次执行循环体，要么令i和j各前进了一步、要么令j回退到了next[j]。

第一种情况：如果我们的模式串太刁钻了，next[j]里面全是-1，我们一次匹配完，要么就是第一个字符就匹配失败，要么就是一直匹配成功，那么匹配失败的字符k=-1占用了一次循环、i++ j++占用了一次循环，而匹配成功的字符占用了二次循环，最后循环体执行了多少次呢？是个[m,2m]范围内的数。
第二种情况：如果我们的模式串中next[j]存在非负的值，即发生了主串不退、子模式串退的情况，看上去似乎模式串可以退至多n次，而主串的每个位置都可能发生模式串的回退，这不就O(m*n)了吗？其实这正是这个算法的一个巧妙之处，模式串向前退x步，说明主串中之前就有x个字符是匹配成功过的。模式串每退的1步都能对应上一次匹配成功，而一次匹配成功也就是一次i++、j++，也就对应上主串的一次前进。整个过程中模式串退步的步数无法超过主串前进的次数，而模式串退步的次数至多也就等于步数（一次一步）。所以，模式串退步的次数（j = next[j]被执行的次数）不会超过主串前进的次数（i++ j++被执行的次数）。和第一种情况相比，多执行了多少次循环？不到m次。所以还是O(m)的。

对于getnext函数，参考上面的分析，其实是一样的。很容易得到getnext的时间复杂度是O(n)。

因此，整个算法的时间复杂度是O(m+n)！

参考

字符串处理 - KMP算法的时间复杂度是如何计算的？ - SegmentFault 思否

（原创）详解KMP算法 - 孤~影 - 博客园 (cnblogs.com)