也许，你可以像我这样来了解KMP模式匹配算法

本文已在本人微信公众号“码农小阿飞”上发布，打开微信搜索“码农小阿飞”，或者者扫描文章结尾的二维码，进入公众号并关注，即可以在第一时间收到我的推文！

前言

不论是什么编程语言，字符串可能不是基本类型之一，但肯定都是最常用的数据类型之一，对于字符串的操作是程序设计中最常见的行为。

在所有对字符串的操作中，字符串的查找匹配似乎又是日常编程中最司空见惯的操作，无论是后台程序根据客户所提交的搜索关键字来匹配，并返回搜索候选内容。还是前台程序根据客户输入的关键字，高亮显示匹配的字符串。

所谓的字符串匹配，就是在一段字符主串中，去匹配和模式串在每个位置上的字符都相同的子串，而模式串就是那串需要判断能否在主串中出现的字符串。高效率的字符串匹配算法，能在运行过程中给解决器较小的负担，能减少客户在程序执行算法匹配过程中的等待时间，给客户一种行云流水般的体验。因而，在编程过程中选择合适的字符串匹配算法显得格外重要

朴素模式匹配算法

可能日常开发过程涉及字符串查找匹配的操作，已经有很多的工具类帮助实现，只需简单的调用就行。授人以鱼不如授人以渔，假如让你手写一个简单的字符串匹配算法，你又会怎样做呢？

说到字符串的匹配，我想大家自然而然最先能够想到的算法应该就是朴素模式匹配算法。所谓的朴素模式匹配算法，就是刚开始的时候将主串的第1个字符和模式串的第1个字符对齐，从模式串的第1个字符开始，从左往右一一比照主串和模式串的字符。假如字符相同，则比照双方的下1个字符。假如其中出现某个位置，主串的字符和模式串对应位置的字符不相同，则将模式串整体往右移动1个字符的位置，继续上述操作，直到在主串中匹配到与模式串完全相同的子串，或者者主串剩余还没有进行比照的字符数量少于模式串的字符数量。

/***** * Java代码实现朴素模式匹配 *  * @param stringS 主串S  * @param stringT 模式串T  */public boolean match(String stringS, String stringT) {    char[] charsS = stringS.toCharArray();    char[] charsT = stringT.toCharArray();    for (int i = 0, sizeI = charsS.length - charsT.length; i <= sizeI; i ++) {        for (int j = 0, sizeJ = charsT.length; j < sizeJ; j ++) {            if (charsS[i + j] != charsT[j]) {                break;            }            if (sizeJ - 1 == j) {                return true;            }        }    }    return false;}

朴素模式匹配算法比较简单，比较容易了解和接受，下面就是朴素模式匹配算法的运行过程：

在这里插入图片形容

从上述运行过程的动态图可以看出，朴素模式匹配算法在字符匹配的过程中，不断的往回移动主串的指针来和模式串进行比照，这种行为称为回溯。在算法运行过程中，大量的指针回溯往往会添加大量的运行时间，效率往往都不高。

既然这么说，那有没有一种算法能避免这种通过主串指针不断回溯来进行字符匹配导致效率降低的问题呢？毫无疑问，有！那就是今天要讲的KMP模式匹配算法。

KMP模式匹配算法在这里插入图片形容

先看上面这张图，主串直到匹配到第6个字符才发现和模式串第6个字符不相同，说明什么？说明主串的前5个字符组成的子串是和模式串的前5个字符组成的子串是相同的，这会是一个很重要的信息。而从模式串可以看出，模式串的前3个字符互不相同。那就没必要像朴素模式匹配算法一样往回移动主串的指针，拿主串的第2和第3个字符去和模式串的第1个字符去做无谓的比较，由于那肯定不相同。

既然如此，先将模式串往右移动，跳过模式串第1个字符和主串第2和第3个字符的比较，这时候模式串第1个字符和主串第4个字符相对齐，模式串第2个字符和主串第5个字符相对齐。

在这里插入图片形容

再回过来看一下模式串，模式串第1个和第2个字符组成的子串“ab”和模式串第4个和第5个字符组成的子串“ab”相同。主串前5个字符组成的子串又是和模式串前5个字符组成的子串是相同的，那么主串的第4个和第5个字符组成的子串就必然和模式串第1个和第2个字符组成的子串相同，在上一次模式串位置滑动后他们恰好逐个对齐，那么主串的指针就没必要再回来比照这两个位置的字符了。

在这里插入图片形容
这样即可以不往回移动主串的指针，又得以继续进行字符比较。这就是KMP算法的核心思想，通过模式串前面的字符和主串对应位置字符的比照结果，再结合模式串自身的前后位置信息，做出适当的滑动，避免主串指针无谓的回溯，从而达到匹配效率上的提升。

你可能会疑问了，我们当然可以非常直观的通过图示对模式串进行解读，可计算机呢？对计算机来说，只能通过循环和判断等方式来处理问题，怎样用代码来让计算机来解读未知模式串的信息呢？

KMP算法-next[]数组推导

KMP算法就是根据模式串的字符前后位置信息生成一个与模式串等长的整形数组next[]，用来存储当模式串上每个位置上的字符假如和主串所对应字符不相同的时候，根据next[]中得到的整型数值作为指引，做一个最优的滑动，什么叫最优滑动呢？那就是模式串往右滑动的尽可能少，这样就能说明左侧依然对齐的部分尽可能的多，也就不会错过可能的子串，同时又能做较少的比较。

在这里插入图片形容

如上图所示就是next[m]=n的例子，上边是模式串移动之前的位置，下边是模式串移动之后的位置。意思是当模式串下标为m处的字符和主串中的字符比照出现不同时，根据next[m]=n指示，往右滑动模式串，使模式串下标为n处的字符和本来模式串下标为m处的字符对应的那个主串中的字符对齐并进行比较，那么，模式串移动前后的位置关系就会如上图所示，模式串下标为m处的字符和模式串下标为n处的字符对齐。

注意此处用的是下标，由于Java语言和很多程序语言一样，数组的下标是从0开始的，这和上文多处提到的第几个字符要注意区分，很多人都由于这两者的关系了解错乱，而导致对后续了解next[]数组的推导过程造成不小的影响。

模式串未移动前m往左所有位置的字符都已经和主串中对应位置的字符逐个相同，移动就是为了避免主串指针回溯进行无谓的比较，所以所有有效的next[m]=n都应该满足性质：假如next[m]=n成立，则n位置往左直到字符串的尽头所有字符和m往左所对应的字符都应该逐个相同，除非n之前不存在任何字符。满足这个条件的n可能会有多个，但是这个n肯定是最大的那种可能。这就是人们常说的最长的公共前缀和最长的公共后缀，是整个next[]数组推导的核心思想，也是后续推导next[]数组的理论基础，这一点必需得搞清楚，由于假如不满足这个性质，所有的滑动都是徒劳，是没有意义的，只会造成误判产生错误。

在这里插入图片形容
结合上述得出的理论基础，再来看一下这张图。假如next[m]=n成立，肯定满足上面的性质。那么假如此时m处的字符和n处的字符正好又相同的话，next[m+1]=n+1就肯定成立，既然m和n往左部分已经生成最长的公共前缀和公共后缀，m处的字符又和n处的字符相同，那next[m+1]=n+1就肯定满足上述性质。

可是，假如m处的字符和n处的字符不相同的话，我们就不能草率的令next[m+1]=n+1，由于这样就不满足上述性质。怎样做？那我们就像是模式串n处的字符比照失败那样，令n=next[n]做一次最优的滑动，m和n仍旧可以满足上述关系，和上面一样，我们继续比较m处和n处的字符能否相同，不相同就继续移动，直到m处和n处的字符相同，又或者者n处不存在字符。可以这么说：在已知所有的next[m]，其中m<n，那么我们即可以根据这些信息推导出next[n]。

在这里插入图片形容
如上图所示，假如在比照过程中，模式串的第1个字符和主串所对应的字符不相同，那么就跳过主串中这个字符的比照，所以next[0]=-1，而且这一点在任何模式串中都成立。那么，结合上面的论述，已知next[0]我们即可以推导出next[1]，已知next[0]和next[1]我们即可以推导出next[2]，以此类推，整个next[]数组我们即可以推导出来。

/** * Java代码实现KMP模式匹配算法next[]推导过程 * * @param stringT 模式串 * */private int[] getNext(String stringT) {    char[] chars = stringT.toCharArray();    int[] next = new int[chars.length];    next[0] = -1;  // 这是一个必然的结果，不论是对什么模式串，以此为突破点往后推导    for (int i = 1; i < chars.length; i ++) {        int j = next[i - 1];        while (true) {            if (-1 == j || chars[i - 1] == chars[j]) {                next[i] = j + 1;                break;            } else {                j = next[j];            }        }    }    return next;}

在这里插入图片形容

验证一下结果，和我们从图示中得到的信息是一样的，再将推导出的next[]数组结合到实际字符串匹配的代码中。

/***** * Java代码实现KMP模式匹配 * * @param stringS 主串S  * @param stringT 模式串T  */public boolean match(String stringS, String stringT) {    char[] charsS = stringS.toCharArray();    char[] charsT = stringT.toCharArray();    int[] next = getNext(stringT);    int j = 0;    for (int i = 0, sizeI = charsS.length; i < sizeI; i ++) {        // 此处0 > j其实就是针对next[j]=-1的情况，跳过主串当前字符的比照        if (0 > j || charsT[j] == charsS[i]) {            j ++;        } else {            j = next[j];            i --; // 实现继续比照主串的同一个位置的字符        }        if (charsT.length == j) {            return true;        }    }    return false;}

看看效果如何。

在这里插入图片形容

KMP算法-next[]数组推导优化

是不是主串的指针没在往回移动？也少去了很多没必要的比较过程？可是我想告诉你的是，还可以再优化优化，假如上述的模式串改为“abcabc”呢？

在这里插入图片形容

根据之前next[]数组推导的结果，结果和我们之前说的一样，结合到实际匹配当中去看看：

在这里插入图片形容
可以看出，在主串第6个字符和模式串第6个字符不相同时，我们根据next[5]=2，滑动模式串，也就是将模式串的第3个字符和主串的第6个字符进行对齐并进行比较。可是我们从模式串中可以知道，模式串的第3个和第6个字符是一样的，也就是说既然主串的第6个字符和模式串的第6个字符不相同，那么也就和模式串第3个字符不相同了。我们只在next[]数组的推导中next[m]=n需要满足最长公共前缀和公共后缀，却忽略了next[]推荐滑动位置的字符能否就是和当前字符相同，假如相同那么也就不需要再做无谓的比较了。

我们对getNext()的代码进行一下优化：

/** * Java代码实现KMP模式匹配算法next[]推导过程 * 针对next[]推荐比照字符相同问题优化 * * @param stringT 模式串 * */private int[] getNextPlus(String stringT) {    char[] chars = stringT.toCharArray();    int[] next = new int[chars.length];    next[0] = -1; // 这是一个必然的结果，不论是对什么模式串，以此为突破点往后推导    for (int i = 1; i < chars.length; i ++) {        int j = next[i - 1];        while (true) {            if (-1 == j || chars[i - 1] == chars[j]) {                next[i] = j + 1;                break;            } else {                j = next[j];            }        }    }    // 优化版增添代码    for (int i = 0; i < next.length; i ++) {        if (0 <= next[i] && chars[next[i]] == chars[i]) {            next[i] = next[next[i]];        }    }    return next;}

在这里插入图片形容

再验证一下，发现变化还是有点多的，在结合图示发现的确没有问题，优化后的代码再结合到实际匹配当中去：

/***** * Java代码实现KMP模式匹配 * * @param stringS 主串S  * @param stringT 模式串T  */public boolean match(String stringS, String stringT) {    char[] charsS = stringS.toCharArray();    char[] charsT = stringT.toCharArray();    int[] next = getNextPlus(stringT);    int j = 0;    for (int i = 0, sizeI = charsS.length; i < sizeI; i ++) {        // 此处0 > j其实就是针对next[j]=-1的情况，跳过主串当前字符的比照        if (0 > j || charsT[j] == charsS[i]) {            j ++;        } else {            j = next[j];            i --; // 实现继续比照主串的同一个位置的字符        }        if (charsT.length == j) {            return true;        }    }    return false;}

现在，再看一下效果：

在这里插入图片形容

简直不要比朴素模式匹配算法快太多，我素材都可以少画不少，哈哈哈 ...

结束语

在编程世界中，处理一个问题的方法往往不止一种，而这些方法之间没有绝对的优劣之分，只是可能当时所处的环境不同罢了。上述例子让我们看到KMP算法比朴素模式匹配算法高效不少，那假如主串是“abcdeabcde”，模式串是“abcde”呢？朴素模式匹配算法不需要指针回溯就能匹配成功，KMP模式匹配算法却多出了一个next[]数组推导的过程。KMP算法的优势是：next[]数组一次推导，四处匹配的特性。

到这里KMP模式匹配算法也就算讲完啦！吃水不忘挖井人，感谢算法创始人D.E.Knuth、J.H.Morris和V.R.Pratt，KMP正是以他们三者名字的首字母组合而来。

假如觉得这篇文章对你理解KMP模式匹配算法和其中next[]数组的推导过程有帮助的话，不胜荣幸。当然，假如对文章有什么疑问，又或者者是文章中有什么地方有误或者者解释不当，请在评论区留言，一起讨论。

关注我，带你去看编程世界中那些有趣的发现。

在这里插入图片形容