字符串匹配算法 字符串匹配算法详解

为了保证代码的严谨性，本文所有代码都在leetcode网站AC上，大家可以放心食用。

在皇帝生日之际，举国欢庆。元吉餐厅作为世界上第一家餐厅，被选为本次庆典的食品供应商。这次庆典对元吉餐厅来说是一次前所未有的挑战。毕竟是第一次庆祝皇帝生日。稍有不慎就是失去理智的大罪。整个元吉餐厅都是紧张的布置。这时，一个酒保突然慌慌张张地跑到楚原报告。发生了什么让酒保如此慌张？

元吉餐厅内

酒保:不，不，掌柜的，出大事了。

楚原:发生了什么事？慢慢说。真是一团糟。

掌柜:皇上按照我们的菜单点了666道菜，我们家做西湖醋鱼的大厨却请假回家结婚了。不知皇帝是否点了这道菜。如果我们做不到，那么我们的店就完了。

楚原:别说那么多。看看皇帝点的菜里有没有这道菜！

找了很久，查了很多遍，最后确定不是皇帝点的这道菜。餐厅里的人都松了口气

通过上面的一个例子，让我们对字符串匹配有一个简单的了解。让我们仔细看看。

字符串匹配:假设给s和t两个字符串，在主字符串s中寻找模式字符串t的过程称为字符串匹配。如果在主串s中找到模式串t，则表示匹配成功，函数返回t在s中第一次出现的位置，否则匹配不成功则返回-1。

示例:

在上图中，我们试图找到模式字符串T = baab，它第一次出现在主字符串S = abcabaabcabac中的位置是红色阴影部分。t第一次出现在s中的位置是下标4，所以返回4。如果模式字符串t没有出现在主字符串s中，则返回-1。

解决上述问题的算法称为字符串匹配算法。今天，我们将介绍三种字符串匹配算法。记得打卡，不确定面试的时候问一下。

BF算法

这个算法很容易理解，就是我们把模式串和主串进行比较，一致的时候继续比较下一个字符，直到比较完整个模式串。如果不一致，将模式字符串向后移动一个位置，再次从模式字符串的第一个位置开始比较，并重复前面的步骤。先来看看这个方法的动画分析，看完肯定能明白。

通过上面的代码，我们可以立刻理解这个算法。让我们用这个算法来解决下面的经典问题。

Leetcdoe 28。实现strStr主题描述

给定一个草垛串和一个针串，找到针串在草垛串中出现的第一个位置。如果不存在，则返回-1。

例1:

输入:草堆=“你好”，针=“ll”输出:2

例2:

输入:haystack = " aaaaa "，needle = "bba "输出:-1

题目解析

其实这个题目很好理解，但是需要注意以下几点，比如我们的模式串为0的时候应该返回什么，我们的模式串长度大于主串长度的时候应该返回什么。让我们看看标题代码。

标题代码

我们来看看BF算法的另一个算法。其实原理是一样的，就是修改代码。看完我们的动画，这一下子就能明白了。您可以通过结合以下代码中的注释和动画来理解它。

BM算法

我们刚才讲了BF算法，但是BF算法是有缺陷的，比如下面这种情况

如上图所示，如果我们使用BF算法，当遇到不匹配的字符时，我们会将模式字符串一次右移一位，然后从头开始重新匹配。我们观察到我们的模式字符串abcdex中的每个字符都是不同的，但是当我们第一次匹配字符串时，abcde匹配成功，但是当X出现时，它就失败了。因为模式串的每一位都不一样，我们不需要一次右移一位，然后可以直接跳过一些步骤。下图

我们可以跳过其中的一些步骤，直接进入下一步。那么我们的原则是什么呢？

不良字符规则

我们之前的BF算法是从前到后比较，而BM算法是从后到前比较。我们看看具体的流程，还是用上面的例子。

BM算法从后往前比较。这时，我们发现比较的第一个字符不匹配。我们把主串称为坏字符，也就是f，找到坏字符后，我们找出模式串T是否包含f这个字符，我们发现没有f，这时候只需要把模式串移到坏字符后面右边的那个。下图

如果发现模式字符串中有不良字符怎么办？见下文

这时我们的坏字符是f，我们发现模式串中有坏字符f，所以我们需要移动模式串t来对齐f和模式串中的坏字符。见下图。

然后我们继续从右向左比较，发现D是一个坏字符，所以我们需要将D和模式字符串中的坏字符对齐。

那么我们来考虑一下这种情况，即如果模式字符串包含多个坏字符怎么办？

那么为什么要把最右边对应的元素和坏字符匹配呢？如果我们在上面的例子中不遵循这个规则，会发生什么？

如果我们不遵守以上规则，我们将错过真正的比赛。我们的主字符串包含babac，但是匹配不成功，所以要遵守最右边对应字符相对于坏字符的规则。

上面我们介绍了三种动作，即在下面的模式串中没有找到与坏字符对应的字符，找到一个对应的字符，找到两个。在这三种情况下，我们移动不同的数字，那么我们决定根据什么来移动数字呢？让我们给图片中的字符加下标。见下文

让我们考虑一下这种情况。

在这个时候，这种情况绝对是不可行的。如果你不向右移动，你甚至可能向左移动。我们有办法解决这个问题吗？继续往下看。

好的后缀规则

好的后缀很容易理解。我们之前说过BM算法是从右向左比较的。让我们看看下面的例子。

在这里，如果我们按照不好的字符移动是不合理的，那么我们可以使用好的后缀规则，那么什么是好的后缀呢？

BM算法从右向左比较。发现不良字符时，cac已经匹配成功，红色阴影中发现不良字符。这时，已经匹配成功的cac就是我们的好后缀。此时，我们在模式字符串中查找它。如果我们找到另一个匹配好后缀的字符串，我们将把另一个匹配好后缀的字符串滑动到它与好后缀对齐的位置。

是不是感觉有点尴尬？没关系。让我们看看下面的图片。红色代表不好的字符，绿色代表好的后缀

我理解上面的情况，但是让我们想想下面的情况

如上所述，如果在模式字符串的头部没有找到后缀，那么找到带有后缀的子字符串就可以了。但是为什么要强调这个头呢？

让我们看看下面这个情况

但是当我们在头部找到后缀子字符串时会发生什么呢？

让我们通过运动图片来看看一个例子的具体执行过程

话虽如此，即使坏字和好后缀的规则都讲完了，坏字也容易理解。让我们总结一下好的后缀

1.如果模式字符串包含一个好的后缀，中间和头部都可以按照规则移动。如果好后缀在模式字符串中出现多次，则以最右边的好后缀作为参考。

2.如果模式串的头部包含一个好的后缀子串，可以按照规则移动，但是中间部分包含一个好的后缀子串。

3.如果模式串末尾不匹配，也就是没有好的后缀，那就按照不好的字符移动。这里有相当多的文章没有提到，这是一个需要特别注意的地方。我在这篇论文中找到了答案。感兴趣的同学可以看一下。

一种快速字符串搜索算法。澳大利亚竞争委员会通讯，1977，10:762-772。

当我们第一次开始谈论坏角色的时候，有没有可能出现负值，也就是向左移动？因此，为了解决这个问题，我们可以分别计算后缀和坏字符向后滑动的数量，然后将这两个数字中最大的一个作为模式串向后滑动的数量。

这张破图真的很费力。我们来看看算法代码。代码有点长。我在网站上标注了评论和AC。如果你感兴趣，你可以看看。如果你不感兴趣，你可以理解不好的字符和好的后缀规则。你可以直接跳到KMP区

让我们看看代码中使用的两个数组。因为两个规则的移动位数只和模式串有关，和主串无关，所以可以提前找出每个情况的移动情况，保存在数组中。

KMP算法

刚才我们讲了BM算法。虽然不是很容易理解，但是用心去看肯定能理解。我们来看一个新的算法，是考研必备的算法。其实BM和KMP算法的本质是一样的。你只需要几分钟就能理解BM和KMP。

我们先来看一个例子

注意:为了让读者更容易理解，我们把指针移动改成了模式串移动，和主串的移动是一致的。重新比较时，我们继续从指针位置进行比较。

我们是否能通过上面的例子快速理解KMP算法的思想，我们继续往下看。

在上面的例子中，我们提到了一个名词，最长的普通前缀。这是什么意思？让我们用一个简单的例子来描述它。

这时我们在红色阴影中匹配失败，绿色是匹配成功的部分，所以我们观察匹配成功的部分。

让我们看看匹配成功部分的所有前缀和后缀

我们最长的公共前缀如下，所以我们需要这样移动它

好了，看完上图，KMP的核心原则已经基本定了，但是我们现在的问题是，怎么知道它最长的公共前缀的长度呢？你怎么知道要移动多少比特？

正如我们刚才在BM中所说，我们移动的位数与主字符串无关，只与模式字符串有关，与我们的BC、后缀和前缀数组的值有关。我们可以知道每次通过这些数组我们移动了多少位。事实上，KMP还有一个数组，叫做next数组。那么下一个数组存储了什么呢？

在我们最长的公共前缀后缀存储在下一个数组中，前缀的结束字符下标。不管是不是觉得有点别扭，我们举个例子来说明一下。

知道下一个数组后，我们的KMP算法就容易实现了。另外，让我们看看下一个数组是做什么用的。

不用说，其余的完全一样。让我们把上面的例子翻译成对应我们开头的动画。

让我们看一下代码，它标有详细的注释。请仔细阅读。

注意:许多教科书对下一个数组的表示不一致，所以你可以理解它们

好吧，好吧，我们先写这么多吧