从一无所有的角度出发，带你一步步实现kmp算法

1. 引言

之前在学习strstr函数时听老师提到过kmp算法这种高效的查找子字符串的算法，介于种种原因一直没找到机会好好研究一下这种算法。

最近难得有点时间了，却发现讲解该种算法的大多数文章都是在已知该算法的前提下来讲解，各种概念的引入都十分突兀，让人难以理解。

除此之外，这些文章要么太长，讲解过于冗杂，要么就是太短，只讲到了表面。

我喜欢从发明某一个东西的角度去学习某个东西，因为这样不仅能使我深入地理解该种算法的原理，也能使我更加好理解各种概念引入的原因，还有利于提升自己的思维和解决问题的能力。

这篇文章旨在从一无所有的角度出发，带领读者一步步“发明出”kmp算法，并使读者能够深入理解该算法的原理内核，及各种概念引入的原因。

2. 什么是kmp算法

kmp算法就是在一个字符串中寻找子字符串的算法，其由D.E.Knuth、J,H,Morris和 V.R.Pratt三位大佬共同提出，所以叫kmp算法。

该算法将解决该问题的时间复杂度，从原本暴力算法的O(n*m)降低到了O(n)，尽管在数据量较小时并不能节省很多的时间，但是对于极大的数据量是很有意义的。

3. 暴力解法

在我们开始学习kmp算法之前，我们先来看看解决寻找子字符串问题的暴力解法。

3.1 思路

1. 首先在被查找字符串（原字符串）中找到要查找字符串（子字符串）的首元素。

2. 然后检查之后的元素是否完全相等。

3. 如果完全相等，则返回原字符串中子字符串的起始地址。

4. 如果存在不相等的元素，则分别回溯指向两字符串的指针，再次从第一步开始重复。

实现写法1：

char* my_strstr(const char* str1, const char* str2)
{
    assert(str1 && str2);

    if(*str2 == '\0')
    return (char*)str1;

    while(*str1)//当*str1为'\0'时循环结束，返回NULL
    {
        while(*str1 != *str2)//找到第一个字符相等的位置
        {
            str1++;
            if(*str1 == '\0')
            return NULL;
        }
        const char* str3 = str1;
        const char* str4 = str2;
        while(*str3++ == *str4++)//检查改位置是否符合条件
        {
            if(*str4 == '\0')
            return (char*)str1;
        }
        str1++;//未返回说明不符合，第一个指针移动一次
    }
    return NULL;
}

实现写法2：

char* my_strstr(const char* str1, const char* str2)
{
    assert(str1 && str2);

    if(*str2 == '\0')
    return (char*)str1;

    int len1 = strlen(str1);
    int len2 = strlen(str2);

    int i = 0;
    int j = 0;

    while(i < len1 && j < len2)
    {
        if(str1[i] == str2[j])//匹配成功。i，j各加1，接下来比较下一对
        {
            i++;
            j++;
        }
        else//匹配失败
        {
            i = i - j + 1;//i回溯到原来的位置并向前位移一次
            j = 0;//j重置为0，从头开始重新匹配
        }
    }

    if(j == len2)//匹配到str2的最后一个元素，说明匹配成功
    return str1 + i - j;
    else
    return NULL;
}

3.2 缺陷

以上两种写法内核相同，我们就以第二种方法来说明。

我们的做法就是逐个匹配，当匹配失败时，使i回溯到刚刚开始匹配的位置的下一个位置，又使j重置为0。

这样一来，我们算法的复杂度就为O(n*m) 。

而且我们会发现，似乎将i回溯到最开始的位置的下一个位置似乎毫无意义，因为作为算法的设计者，我们知道回溯到的那个位置，在上一次匹配时是与子字符串中的B匹配的。

那么，我们能不能让程序也利用起上一次匹配留下的信息，来使得回溯的距离减小或者根本不回溯呢？

4. kmp算法

4.1 让i不回溯

根据刚才的分析，我们知道，暴力算法有很大的优化空间。优化的点就在于减少回溯的距离或者说根本不回溯。

于是，我们尝试让i不进行回溯，这样，我们就只需要遍历一次原字符串，在原字符串明显长于子字符串时，算法的复杂度就会降低到O(n)。

我们可以通过观察看到，在原字符串中，子字符串的起始位置的下标是2。但经过第一次匹配之后，i就已经为4了，那么我们如何完成匹配呢？

我们可以减少j回溯的距离，形成这样的效果

也就是说，让i不回溯是行得通的。 

那么，我们怎么知道可以让j少回溯呢？怎么知道少回溯多少呢？又如何利用上一次匹配的信息呢？

4.2 相同的前缀后缀

1. 我们发现，在这个例子中，j之所以能够少回溯，是因为j回溯位置之前的两个字符刚好能够与i之前的两个字符相匹配。

2. 我们能够从上一次匹配中得到的信息就是，子字符串的前四个字符与i前方的四个字符是可以匹配的。

3. 结合1，2点我们会发现，其实就是子字符串的前两个字符能与第三和第四个字符分别匹配。原字符串已经匹配过的内容与子字符串的相应部分完全相同，所以自然能够得到第1点。

4. 所以，我们让j回溯距离减小的本质，就是使得相同的前缀和后缀相匹配。

5. 当相同前后缀的长度为2（AB）时，我们就可以使j少回溯2个字节的距离，使得前缀与后缀相匹配。

6. 也就是说，我们只要知道上一次完成匹配部分的相同前后缀的长度，我们就能知道应该让j少回溯多少。

7. 为了方便，我们将每个位置所对应的最长相同前后缀的长度存在一个数组之中，每次遇到不匹配的情况时，访问该数组就能知道让j回溯多少。

4.3 next数组

这个数组就用于存储每个位置对应的最长前后缀的长度。

也就是从数组开头到当前位置的字符串，的最长前后缀的长度。

例如，

在刚才所给的例子中，第一次匹配失败时，已匹配的字符串为“ABAB”，其最长共同前后缀为“AB”。于是第二个B的位置对应的next数组的值就为2。

同理，第二个A所对应的字符串为“ABA”，其最长共同前后缀为“A”。于是第二个A的位置对应的next数组的值就为1。

得到next数组的过程，其实就是在后缀中找前缀，这与查找子字符串很相似，但是不同于查找子字符串，我们只需要知道匹配的有多长即可。

我们用两个指针分别指向前后缀（i，j），如果当前字符匹配，我们就对i，j各加一以匹配下一对，此时，i的值就是前后缀的长度。如果不匹配，我们就进行回溯

既然与查找子字符串的过程很相似，那么我们在找前缀的过程中就可以利用起创建到一半的next数组。

int* build_next(const char* str)
{
    assert(str);
    int len = strlen(str);
    int* next = (int*)malloc(sizeof(int) * len);
    int common_len = 0;//记录共同前后缀长度
    int i = 1;
    next[0] = 0;//第一个位置对应的字符串只有一个元素，无前后缀之说
    while(i < len)
    {
        if(str[common_len] == str[i])//前后缀匹配成功，长度加一，并保存在当前位置
        {
            common_len++;
            next[i] = common_len;
            i++;
        }
        else//前后缀匹配失败
        {
            if(common_len == 0)
            {
                next[i] = 0;
                i++;
            }
            else
            common_len = next[common_len - 1];//利用已创建的部分next数组，使得common_len少进行回溯
        }
    }
    return next;
}

4.4 全部代码

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>

int* build_next(const char* str)
{
    assert(str);
    int len = strlen(str);
    int* next = (int*)malloc(sizeof(int) * len);
    int common_len = 0;//记录共同前后缀长度
    int i = 1;
    next[0] = 0;//第一个位置对应的字符串只有一个元素，无前后缀之说
    while(i < len)
    {
        if(str[common_len] == str[i])//前后缀匹配成功，长度加一，并保存在当前位置
        {
            common_len++;
            next[i] = common_len;
            i++;
        }
        else//前后缀匹配失败
        {
            if(common_len == 0)
            {
                next[i] = 0;
                i++;
            }
            else
            common_len = next[common_len - 1];//利用已创建的部分next数组，使得common_len少进行回溯
        }
    }
    return next;
}

char* kmp_search(const char* str1, const char* str2)
{
    assert(str1 && str2);
    int* next = build_next(str2);

    int i = 0;
    int j = 0;
    while(i < strlen(str1))
    {
        if(str1[i] == str2[j])//匹配成功，i，j各加一以匹配下一对
        {
            i++;
            j++;
        }
        else if(j > 0)//匹配失败，根据已匹配部分的最长共同前后缀长度回溯j
        j = next[j - 1];
        else//第一个字符就不匹配
        i++;
        
        if(j == strlen(str2))
        return (char*)str1 + i - j;
    }

    return NULL;
}

int main()
{
    char* arr1 = "abababcabc";
    char* arr2 = "ababc";
    printf("%s\n", kmp_search(arr1, arr2));
    return 0;
}

5. 总结

这就是我所理解的kmp算法，核心有两个：

1. 让i不回溯，这是让时间复杂度降低的根本所在。

2. 根据上一次匹配留下的信息，使子字符串的前缀与已匹配部分的后缀相匹配。

当然，如果对我的理解有异议或是有疑问的，都欢迎在评论区提出，我会积极回应修改。

总的来说，kmp并不难，就是引入的概念较多，学习时找不到好的切入点。

在大多数情况下，暴力算法其实并不比kmp算法差很多，而且较好理解，较好实现。