【算法】高效"KMP"字符匹配算法就这么简单

1、聊一聊

    今天跟大家推荐的是一首重量级的钢琴曲中文名为《克罗地亚狂想曲》，一般人听这个曲子可能觉得比较亢奋，如果大家了解一下克罗地亚战争就会发现其实它是如此的悲伤。

    本篇文章如约而至，很多小伙伴在理解KMP字符匹配算法有点难度，所以bug菌这里带大家学习一下，具体应用可以参考<【算法】"暴力"字符匹配算法的C语言实现>。

2、KMP算法介绍

1

KMP介绍

    KMP是一种字符匹配算法，为啥叫KMP呢？因为是由D.E.Knuth，J.H.Morris和V.R.Pratt大佬提出来的。那一些小伙伴会问了怎么不叫"DJV算法"呢?因为老外都是名字在前，姓氏在后。

    说实在的bug菌初次接触这个字符匹配算法的时候也是一脸懵逼，那时候也是找了很多的资料来理解、分析和推导等等，很多知识回头一看也就那么回事，想不明白那时候怎么会觉得那么复杂,或许这就是对未知事物的一种敬畏吧。

    KMP算法说到底和暴力字符匹配功能上是一模一样的，就是查找匹配字符串在主字符串中的位置，如果只是应用完全可以不用理会它是怎么实现的，调用几个函数->传递几个参数->得到结果,然后记得他比暴力匹配高效一点就行了。好了，本文看来要收尾了。

2

还不能结束

    其实我们学习理论知识并不是学习知识本身，而是要学习了以后能够获得一种解决问题的办法和思路。前面那篇文章为大家讲解了暴力匹配，也跟大家在文中留了一个问题，假如没有KMP算法我们是否有思路去更好的优化匹配效率呢?等思考完后再来看看KMP是如何处理该问题的。

    KMP算法的核心 : 就是尽可能利用更多匹配过程中的信息来减少匹配串与主串的匹配次数从而提高匹配效率。

3、原理分析

1

几个实例分析

    那肯定得把暴力匹配中需要优化的匹配过程拿过来，如下图所示:

    匹配完abab以后匹配失败，按照暴力匹配会把模式串移动一个字节继续重头开始匹配，然而再次匹配必定不成功，得继续把模式串移动一个字节进行匹配。

    前面我们讲到KMP算法利用已经进行过匹配过的信息进行优化匹配，如上图当进行第一次匹配以后，我们能够利用的信息有两个：1)模式串信息；2)已经匹配过的ababa信息，其他信息暂且还未知。

    那么就简单点处理 : 如果已经匹配的字符串前两个字节与后面两个字节相等，那么就把模式串移动两个位，继续跟主串比较即可,因此从第三个字符开始进行接下来的匹配，无需重头开始匹配，最终匹配成功。

    上图是最简单的情形，那么下面我们看另外一种情况:

    按照之前的做法，如果已经匹配过的aaaa中前两个字节等于后两个字节，那么模式串应该移动两个字节，然而我们发现其只需要移动一个字节就能匹配成功了，看来仅仅用之前的策略还不够完善，还得补充其它策略才行。

2

总结规律获得算法

    通过前面两个例子了解到，我们只需要通过一套统一的规律来指导第A个字符匹配不成功以后下一步该对第B个字符进行匹配即可。于是就形成一张映射表-next数组表（不用太纠结名字，主要的意思是下一步该如何动作所以叫next）。

    这个next数组表是通过模式串获得的，首先给大家看看一个next表:

分析一下：

• 1)第一行就是模式串的各个字符，第二行是数组的标号，因为到时候会定义一个next[5]数组存放表格中的信息。

• 2)"前后缀等"表示的是包含比较失败字符串在内的字符前后缀相等的最大字符长度，而next值是前后缀向右填充并在前面补-1得到的数组值。结合下图和表格中的数据字符对应的next值是对应得上的。

• 3)那么我们可以检验一下，字符C比较失败以后从匹配字符[2]继续匹配，即模式串的第三个字符，跟之前的分析一致。

• 4)同样我们来看看aaaac模式串的next数组图:

• 5)同样加入我们在第3个a匹配失败和最后一个c匹配失败以后如何获得前后缀的呢?如下图所示，前面的例子没有重叠的前后缀出现，不过这里就出现了重叠的问题。

• 6)很明显如果字符C匹配失败，对应的需要从模式串[3]继续比较，即模式串的第四个字符继续比较，与前面的分析一致。

• 7)如果大家还看不懂前后缀，那bug菌再画一个图，你肯定就懂了:

4、KMP算法的C实现

1

实现代码

    对于KMP算法的代码实现真的非常巧妙，而且特别的简短，如下是KMP算法的实现，KMP算法目前也存在比较多的改进版本，大家常用的还是如下实现:

  1#include <stdio.h>
  2#include <stdlib.h>
  3#include <string.h>
  4
  5#define NEXT_LEN 6
  6
  7char *Parent = "1234567891212123456789";
  8char *Chind  = "121212"; 
  9int  next[NEXT_LEN] = {0};
 10
 11/******************************************************
 12 * Fuction：KMP匹配算法查询函数 
 13 * Params : str1:主串；str2:模式串；next:next数组
 14 *         (公众号 : 最后一个bug) 
 15 *****************************************************/
 16char* KMP(const char * str1, const char * str2,int * next) 
 17{
 18    int i = 0; 
 19    int j = 0;
 20    char * ret = (char*)str1;
 21
 22    while (i < strlen(str1) && j < (int)strlen(str2)) //主串结束、模式串成功 
 23    {
 24        //j = -1直接到next[0]处理或者字符匹配成功
 25        if ((j == -1)||(str1[i] == str2[j])) 
 26        {
 27            //下一个字符移动 
 28            i++; 
 29            j++;
 30        }
 31        else 
 32        {
 33            //如果匹配不成功通过j(模式串比较失败地址)找到next中下一次与主串比较的模式串地址 
 34            j = next[j]; 
 35        }    
 36    }
 37
 38    if (j == strlen(str2))//表示的是模式串全部匹配 
 39    {
 40       return (ret + i - j);
 41    }
 42    else 
 43       return(NULL);
 44}
 45/******************************************************
 46 * Fuction：KMP匹配算法next数组生成 
 47 * Params : str:模式串；next:next数组
 48 *         (公众号 : 最后一个bug) 
 49 *****************************************************/
 50void getNext(const char * str, int * next)
 51{
 52    next[0] = -1;
 53    int i = 0, j = -1;
 54
 55    while (i < (strlen(str) - 1))
 56    {
 57        if ((j == -1 )||(str[i] == str[j]))//通过模式串自身对比获得next数组值 
 58        {
 59            ++i;
 60            ++j;
 61            next[i] = j;
 62        }   
 63        else
 64        { 
 65            j = next[j];
 66        }
 67    }
 68}
 69
 70/******************************************************
 71 * Fuction：暴力匹配算法 
 72 * Params :str1:主串；str2:模式串 
 73 *        (公众号 : 最后一个bug) 
 74 *****************************************************/
 75char *strstr(const char *str1, const char *str2)
 76{
 77    char *cp = (char*)str1;
 78    char *s1, *s2;
 79
 80    if (!*str2)
 81        return((char *)str1);
 82
 83    while (*cp)
 84    {
 85        s1 = cp;
 86        s2 = (char *)str2;
 87        while (*s1 && *s2 && !(*s1 - *s2))
 88        {
 89            s1++, s2++;
 90        }  
 91
 92        if (!*s2)
 93            return(cp);
 94
 95        cp++;
 96    }
 97    return(NULL);
 98}
 99
100/******************************************************
101 * Fuction：对比主函数 
102 * Author : (公众号 : 最后一个bug) 
103 *****************************************************/
104int main(int argc, char *argv[]) {
105    int result = 0;
106    int i = 0;
107    //获得KMP的next数组 
108    getNext(Chind,next);
109    for( i = 0; i < NEXT_LEN;i++)
110    {
111      printf("Next[%d] = %d\n",i,next[i]);  
112    }
113    //进行KMP匹配 
114    result = KMP(Parent,Chind,next)- Parent;
115    printf("KMP    result = %d\n",result);
116    //进行暴力匹配 
117    result = strstr(Parent,Chind) - Parent;
118    printf("strstr result = %d\n",result);
119
120    return 0;
121}

运行结果如下：

分析一下：

• 大家仔细阅读了会发现，其实求next数组和KMP匹配算法是非常的相似，KMP算法的关键就是求next数组，一旦匹配不成功就会去next数组中找下一个模式串的匹配点，再次拿着该匹配点与匹配失败主串进行比较.

• 所以KMP算法的优越之处在于不再需要重头开始比较，其主串的比较指针是不会倒退的。至于两个算法的时间上的复杂度KMP<strstr，这一部分的推导bug菌就不深入分析了，大家有时间可以查阅一下相关资料进行进一步阅读和学习，具体的应用bug菌在前面的暴力匹配有跟大家讲解过，这里就不在赘述了。

5、最后小结

    KMP算法就跟大家介绍到这里了，希望大家能有新的收获，算法的话大家也不需要死记硬背，基本到处都能够找到，了解原理并且能够获得这种处理问题的思维就达到学习的目的了。

    好了，这里是公众号:“最后一个bug”，一个为大家打造的技术知识提升基地。同时非常感谢各位小伙伴的支持，我们下期精彩见！

   如果有想加入公众号群聊共同讨论技术的小伙伴可以添加下方bug菌微信！

推荐好文  点击蓝色字体即可跳转