KMP算法笔记

KMP算法是一个比较抽象的算法，但是由于其算法格式是固定的，即使我们不知道原理仅仅把算法背下来也是不影响使用的，毕竟要比暴力算法快很多。但是，如果我们能将KMP算法真正理解的，即使不去背算法，也能根据它的原理自己手写一遍。

前导知识

对于字符串匹的问题，我们一般会想到用暴力算法，但是暴力算法的时间复杂度比较高，原因在于它可能会把要匹配的某个字符匹配多次，而实际上我们只需要一次就行，这就造成了很多没必要的动作。

举一个非常简单的例子，就是用aaaaaaaab去字符串aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab中匹配，暴力算法每次字符b不匹配的时间，都会重新进行回溯。这就像一个强迫症患者一样，非要进行多次确认，但是这样的行为却没有意义。

KMP算法

原理

每当一趟匹配过程中出现字符比较不等时，不需要进行回溯操作了，而是利用已经得到的匹配备份的结果将要匹配的字符串向右滑动尽可能远的一段距离后，继续进行比较。

这里可以简单的理解为强迫症患者被治好了，不会再去重复的做一些行为了。

假设主串为s₁s₂...s_n，模式串为p₁p₂...p_m，为了解决暴力匹配算法重复匹配的问题，我们需要做到下面的要求：

当匹配过程中产生“失配”（即s_i != p_j）时，模式串要“向右滑动”尽可能远的距离，简单来说，当主串中第i个字符与模式中第j个字符“失配”（即比较不等）时，主串中第i个字符（i指针不进行回溯）应与模式中哪个字符再比较呢？

下面我们继续用暴力算法的思路进行分析，由于主串是在第i个字符与模式中第j个字符“失配”的，所以我们可以得到下面的式子：

p₁p₂...p_j-k+1p_j-k+2...p_j-1 = s_i-j+1s_i-j+2...s_i-k+1s_i-k+2...s_i-1

但是这个式子太长了，我们只需要后面的一部分：

p_j-k+1p_j-k+2...p_j-1 = s_i-k+1s_i-k+2...s_i-1　（1）

失配之后，暴力算法回溯后，继续进行匹配，假设不久后我们又匹配到了主串的第i个字符（这是必然发生的事情，举个例子：一棵大树有3米高，你把它砍成了1米高，但是不久的将来它还是会长到3米高），那么此时主串的第i个字符应与模式串中第k（k < j）个字符继续比较（这里举个例子：你总不可能年龄比你爸还大），则模式中前 k - 1个字符串必须满足下列关系式：

p₁p₂...p_k-1 = s_i-k+1s_i-k+2...s_i-1　（２）

因此，由式子（1）和式子（2）我们可以退出下面的公式：

p₁p₂...p_k-1 = p_j-k+1p_j-k+2...p_j-1 （3）

那么对于上面的主串中第i个字符（i指针不进行回溯）应与模式中哪个字符再比较呢？这个问题，我们是不是可以直接将模式串滑到p_[k]，让p_[k]和s_[i]进行比较，这不就完美解决问题了吗。

有了（3）公式后，我们可以先对于模式串生成一个next数组，令next[j] = k，而next[j]表示当模式串中第j个字符与主串中相应字符失配时，在模式串中需要重新和主串的该失配字符进行比较的字符的位置。在根据公式（3），我们可以引出模式串的next函数的定义：

当j = 1时， next[j] = 0
next[j] = Max {k | 1 < k < j且p₁p₂...p_k-1 = p_j-k+1p_j-k+2...p_j-1}，当此集合不为空时
next[j] = 1 ，其他情况

对于字符abaabcac来说，我们可以用上面的定义推出下面的next函数值：

j	1	2	3	4	5	6	7	8
模式串	a	b	a	a	b	c	a	c
next[j]	0	1	1	2	2	3	1	2

注意：上面的字符串数组第0个位置不是用来存放字符的，而是存放字符长度的，也就是说字符串是从第1个位置开始，但是从这里开始的后面部分，全部采用标准的字符串存储公式。

由此可以引出我们的next数组算法：

get_next

// 求模式串 str 中的 next 数组值，并把值放入 next 数组，空间需要提前分配
inline static void get_next(char *str, int *next, int length)
{
    int i, j;

    i = 0;
    j = -1;
    next[0] = -1;

    while(i < length - 1)
    {
        if(j == -1 || str[i] == str[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            // 回溯
            j = next[j];
        }
    }
}

前面定义的next函数在某些情况下尚有缺陷。例如模式aaaab在和主串aaabaaaab匹配时，当i = 4、j = 4时s.ch[4] != t.ch[4]，由next[j]的指示还需进行i = 4、j = 3, i = 4、j = 2, i = 4、j = 1这三次比较。实际上，因为模式中第1、2、3个字符和第4个字符都相等，因此不需要再和主串中第4个字符相比较，而可以将模式一次性向右滑动4个字符的位置直接进行i = 5, j = 1时的字符比较。

get_next优化

// 求模式串 str 中的 next 数组值，并把值放入 next 数组，空间需要提前分配
inline static void get_next(char *str, int *next, int length)
{
    int i, j;

    i = 0;
    j = -1;
    next[0] = -1;

    while(i < length - 1)
    {
        if(j == -1 || str[i] == str[j])
        {
            i++;
            j++;

            if(str[i] != str[j])
            {
                next[i] = j;
            }
            else
            {
                next[i] = next[j];
            }
        }
        else
        {
            // 回溯
            j = next[j];
        }
    }
}

对比

两个get_next函数对于模式aaaab的执行情况如下：

j	1	2	3	4	5
模式	a	a	a	a	b
next1[j]	-1	0	1	2	3
next2[j]	-1	-1	-1	-1	3

从上面可以看出，后面的get_next函数确实更优秀。

KMP

// str 为主串，fin为模式串
// 成功的话返回第一次匹配到的位置，失败返回-1
int KMP(char *str, int str_length, char *find, int find_length)
{
    int i = 0, j = 0;
#ifndef _STDLIB_H
#include <stdlib.h>
#endif
    int *next = malloc(sizeof(int) * find_length);

    get_next(find, next, find_length);

    while(i < str_length && j < find_length)
    {
        if(j == -1 || str[i] == find[j])
        {
            // 判断成功则后移
            i++;
            j++;
        }
        else
        {
            // 失配则利用next数组移动
            j = next[j];
        }
    }
    free(next);
    next = (void *)0;

    if(j == find_length)
    {
        return i - find_length;
    }
    else
    {
        return -1;
    }
}

完整代码

// 求模式串 str 中的 next 数组值，并把值放入 next 数组，空间需要提前分配
inline static void get_next(char *str, int *next, int length)
{
    int i, j;

    i = 0;
    j = -1;
    next[0] = -1;

    while(i < length - 1)
    {
        if(j == -1 || str[i] == str[j])
        {
            i++;
            j++;

            if(str[i] != str[j])
            {
                next[i] = j;
            }
            else
            {
                next[i] = next[j];
            }
        }
        else
        {
            // 回溯
            j = next[j];
        }
    }
}

// str 为主串，fin为模式串
// 成功的话返回第一次匹配到的位置，失败返回-1
int KMP(char *str, int str_length, char *find, int find_length)
{
    int i = 0, j = 0;
#ifndef _STDLIB_H
#include <stdlib.h>
#endif
    int *next = malloc(sizeof(int) * find_length);

    get_next(find, next, find_length);

    while(i < str_length && j < find_length)
    {
        if(j == -1 || str[i] == find[j])
        {
            // 判断成功则后移
            i++;
            j++;
        }
        else
        {
            // 失配则利用next数组移动
            j = next[j];
        }
    }
    free(next);
    next = (void *)0;

    if(j == find_length)
    {
        return i - find_length;
    }
    else
    {
        return -1;
    }
}

总结

考研经常会考KMP算法的next的数组，所以对于next数组的原理一定要熟悉掌握。

资料来源：《数据结构》严蔚敏版