串的朴素模式匹配算法
- 导读
- 一、串的模式匹配
- 1.1 模式匹配是什么？
- 1.2 为什么要有模式匹配算法？
- 二、朴素模式匹配算法
- 2.1 算法底层逻辑
- 2.2 算法实现
- 2.2.1 过程解析
- 2.2.2 思路分析
- 2.2.3 思路总结
- 2.2.4 代码编写
- 数据类型
- 函数的三要素
- 函数主体
- 2.2.5 代码测试
- 2.2.6 代码展示
- 三、朴素模式匹配算法的缺陷
- 结语
导读
大家好，很高兴又和大家见面啦！！！
经过前面的内容介绍，相信大家现在已经对串这个数据结构有一定的了解了，并且也能够动手实现串的一些基础操作了。
从今天的内容开始，我们将进入串的重要知识点的学习——模式匹配算法。今天的内容会带领大家认识什么是串的模式匹配，并且能够深入理解最简单的模式匹配算法。不知道大家现在是否开始有些期待了呢？那么我们就直接进入今天的主题吧！！！
一、串的模式匹配
1.1 模式匹配是什么？
要理解串的模式匹配，首先我们就需要知道什么是模式匹配。
匹配我们可以理解为配对，对于字符而言，能够凑成一对的只有相同的字符，因此字符的匹配就是寻找相同的字符。而模式匹配我们可以理解为有一个固定的模版，我们要寻找与模板相同的内容。在字符串中，模式匹配指的就是给定一个字符串，然后在另一个字符串中寻找与这个字符串相同的字符串。
在字符串的基本操作中，串的比较和串的定位都是需要判断两个字符串是否相同，但是我们通常将串的定位操作称为串的模式匹配。在串的定位操作中，我们需要在主串中寻找子串的位置，寻找的这个子串我们将其称为模式串，所以寻找与模式串相匹配的字符串就是串的模式匹配。
1.2 为什么要有模式匹配算法？
现在有朋友就会提出来了，咱们在上一个篇章中不是已经介绍了串的定位操作吗，为什么这里还要介绍呢？
对于这个问题大家可以回想一下，在上一篇基本操作中我们是如何实现串定位的操作的？没想起来的朋友也没关系，这里我帮大家回忆一下。
在上一篇我们实现的堆分配定位操作中，代码主体可以分为两个部分——1.堆分配存储预处理部分；2.定位操作部分。完整代码如下所示：
//串的定位操作
int Index(HString S, char* T) {
//堆分配存储的预处理部分
if (!T)//判断串T是否为空指针
return -2;//串T为空指针时，无需执行定位操作
int len = StrLength(T);//获取串T的串长
if (len == 0)//判断子串T是否为空串
return -3;//子串T为空串，则无需查找
char* sub = (char*)calloc(len + 1, sizeof(char));//为子串申请空间
//定位操作部分
for (int i = 1; i <= S.length; i++) {
//从主串首元素开始寻找与串T长度相同的子串
if (SubString(&sub, S.ch, i, len))
//找到子串后判断子串sub与串T是否相同
if (StrCompare(sub, T) == 0)
return i + 1;//相同则返回子串的位序
}
return -1;//当找完串S中的所有子串都未找到，S中不存在与T相等的子串
}
预处理部分主要是为了能够让程序正常运行，而对一些可能产生的问题所做的处理，这里我就不再过多赘述。现在我们主要来看定位操作部分。
我们在进行定位操作时，借助找子串操作，从主串中的首元素开始，依次寻找与串T也就是模式串长度相同的子串；每一次找到的子串，我们都会借助串比较操作来将找到的子串与模式串进行匹配。
这样一看，感觉字符串的模式匹配好像也怎么难呀，这不是只要有找子串操作和串比较操作我们就可以实现了吗？
现在我们就需要思考一下，你能够保证，每次在遇到串的问题时，你都有时间来手搓一份串的基本操作吗？
答案是否定的，很多时候我们遇到的问题可能都仅仅是需要在主串中寻找与模式串相同的字符串，对它在主串中的位置，我们并不需要关注，而且每次都手搓一份串相关的基本操作也是比较麻烦的，因此我们就需要编写一份不需要依靠任何串的基本操作就能实现的模式匹配算法。
今天我们要介绍的就是模式匹配算法中最简单也是最直接的朴素模式匹配算法。下面我们就来谈谈如何实现朴素模式匹配算法。
二、朴素模式匹配算法
朴素模式匹配算法看名字感觉应该不那么好理解，其实说直白一点朴素模式匹配算法就是直接在串定位操作中奖找子串和串比较的部分由原先的调用对应的基本操作改为用代码实现而已。之后就能够直接对模式串与主串进行暴力匹配，因此这种算法又被称为暴力模式匹配算法。
2.1 算法底层逻辑
朴素模式匹配算法的底层逻辑并不难，一句话概括就是先找子串再匹配，如下所示：
从上图中可以看到，在实际的匹配过程，子串并不是与模式串的所有元素进行匹配，因此，朴素匹配模式相比于直接将找子串与串比较改写成代码而言还要简洁一点。我们只需要在主串中一个字符一个字符的与模式串的各个元素进行匹配，匹配相同数量就行，如下所示：
相信大家现在应该就能明白朴素模式匹配算法的底层逻辑了，接下来我们就需要探讨一下如何实现朴素模式匹配算法了；
2.2 算法实现
2.2.1 过程解析
在进行模式匹配时，我们需要完成三个工作：
- 找子串中的元素
- 记录子串的起始位置
- 与模式串进行匹配
在之前的实现中，我们是将这三个工作分开进行，这也就是找子串操作和串比较操作，但是现在我们需要思考的是这些工作能不能同时进行呢？
在前面的演示中我们可以看到，当我们在进行朴素模式匹配时，实际上的操作过程是：
- 找到子串的第一个元素后记录该元素的位置；
- 将找到的子串元素前与模式串中同位序的元素进行匹配；
- 匹配成功则继续寻找下一个元素，匹配失败则继续寻找下一个子串；
下面我们就需要思考如何通过代码来实现这个过程。
2.2.2 思路分析
- 记录子串第一个元素的位置
如果要实现这个功能，我们首先就需要判断子串的第一个元素，这时就会遇到两种情况：
- 子串为空串；
- 子串非空串；
在程序开始运行时，我们在主串中找到的第一个元素肯定是子串的第一个元素，对于子串而言，在开始查找元素之前，我们可以将其视作一个空串；
当后续匹配过程中出现不匹配的情况时，为了记录下一个子串的第一个元素，此时我们则需要将子串清空，这样才能确保下一次记录的元素为下一个子串的第一个元素。
那现在问题来了，我们应该如何查找主串中的元素，以及我们又应该如何记录的子串元素呢？
对于字符串而言，它其实可以看做是一个字符数组，只不过与数组不同的是，对于常量字符串来说，字符串中的元素是无法进行改变的，如下所示：
但是对于常量字符串而言，我们同样也可以通过下标来访问字符串中的元素，如下所示：
因此不管是常量字符串还是由字符数组的形式实现的字符串，串中的元素我们都可以根据它所对应的下标来实现元素的访问。
因此在朴素模式匹配中不管是主串中的元素访问还是模式串中的元素访问，我们都可以借助数组下标来完成。而对于数组而言，下标之间的差值就是两个下标之间的元素个数，因此，我们想要记录主串中找到的子串的内容，我们只需要记录首元素下标和最后一个元素的下标就可以实现。
- 将主串中找到的子串元素与模式串中同位序的元素进行匹配
前面也介绍过，所谓的匹配实际上就是判断两个元素是否相等。对于主串而言，记录子串尾元素下标的变量在每一次查找新的元素时都会与记录模式串元素下标的变量一起同步改变，因此，实际的匹配过程两个相互匹配的对象为子串的尾元素和模式串中同位序的元素进行匹配。
- 匹配成功与匹配失败的处理
当我们在进行匹配成功时，我们则需要在主串和模式串中寻找下一个元素进行匹配，因为我们此时是通过数组下标进行的元素访问，因此在匹配成功时，我们只需要通过改变主串和模式串的元素下标即可。
当我们在匹配失败时，我们则需要寻找下一个子串。这时对于模式串而言，则需要从头开始访问模式串中的元素，因此匹配失败时，模式串的下标需要改为首元素对应的下标；对于主串而言，因为我们是通过记录收尾元素下标而实现的记录查找的子串所对应的元素，因此当我们要查找下一个子串时，我们则需要同时改变记录子串首尾元素的下标。
2.2.3 思路总结
经过前面的分析，现在我们就可以整理出实现朴素模式匹配算法的整体思路了，如下所示：
- 创建三个整型变量如x/y/z，由x记录主串中正在查找的子串的首元素下标，y记录主串中正在查找的子串尾元素下标，z记录模式串中正在进行匹配的元素下标；
- 在匹配的过程中，通过y记录的下标所对应的主串元素与z记录的下标所对应的模式串元素进行匹配：
- 匹配成功：x记录的元素下标不变，同时改变y和z记录的下标并进行下一次匹配；
- 匹配失败：x记录的元素下标改变为下一个子串的首元素下标，y记录下一个子串的尾元素下标，z从模式串的首元素下标开始重新记录；
- 有两种情况可以结束匹配：
- 当主串中找到了与模式串相匹配的子串时，结束匹配；
- 当主串中的子串全部与模式串匹配完时，结束匹配；
为了更好的理解这个算法思路，下面我们来看一下该思路所对应的算法演示：
相信大家看完演示应该对这个匹配过程十分清楚了，接下来我们就可以根据具体的思路来编写对应的代码了。
2.2.4 代码编写
数据类型
在上一篇中我们是通过堆分配存储实现的串的基本操作，为了防止大家的编码思维固化，在今天的算法实现中，我们将通过定长顺序存储的串类型来实现。串对应的数据类型定义如下所示：
//定长顺序存储
#define MAXSIZE 255//最大串长
typedef struct StackString {
char ch[MAXSIZE];//存储字符的数组
int length;//当前串长
}SString;//重命名后的数据类型名
函数的三要素
在编写算法前，我们先要明确自定义函数的三要素：函数名、函数参数、返回类型。
- 函数名
前面也介绍过，串的定位操作就是串的模式匹配，因此，这里我们同样还是把朴素模式匹配算法的函数名命名为Index；
- 函数的返回类型
函数的返回类型可以是char*、int、bool……具体的返回类型可以根据自己的需求来进行定义。这里我们是以记录下标的方式实现，所以我们简单一点就以整型为函数的返回类型；
- 函数参数
在朴素模式匹配中，我们需要的主要是两个元素——主串与模式串。因此函数的参数肯定就是主串与模式串这两个参数。
这里我要重点说明的是参数的类型，在王道书上给出的两个参数的参数类型都是定长顺序存储的类型，并且王道书上是仅通过记录串长的整型变量来实现的串，为了使串中的元素下标与串的位序一一对应，王道书上采用的是将数组下标为0的元素空间给舍弃掉。
但是我自己实现的定长顺序存储是以我们熟悉的在字符串末尾增加'\0'并且通过整型变量来记录串长的形式实现的串。这二者所对应的逻辑形式如下所示：
可能有朋友会很奇怪，为什么我不直接按照书上的方式来实现呢？这样省时又省力。这里我需要说明一下：我相信大家一提到字符串，脑海中出现的肯定是末尾带上'\0'的字符串，肯定很难联想到只有字符元素和串长的字符串。
因此为了将本章的知识与前面所学的内容联系起来，所以我选择以字符串末尾加上'\0'并且通过整型空间来记录当成串长的形式来学习串这个章节的知识点。大家自己在实现的过程中，可以根据自己的学习习惯进行选择。题外话就到这里，接下来我们继续回到主题今天的主题。
对于朴素模式匹配的参数类型，我选择的是主串以定长顺序存储类型，模式串以字符指针的类型来实现，因此函数声明的代码如下所示：
//朴素模式匹配算法
int Index(SString S, char* T);
函数主体
在函数主体中，我们在进行模式匹配前，需要先对特殊情况进行处理。在我们现在要实现的模式匹配中可能会出现的情况就是模式串的参数T为空指针以及模式串为空串，当出现这两种情况时，后续的操作就没有必要实现了，因此，我们需要对这两种情况优先处理，如下所示：
if (!T || strlen(T) == 0)
return -1;
这里的返回值大家根据自己选择的存储形式来定，如果数组下标为0的空间被舍弃了，那此时我们就可以返回0；如果数组下标为0的空间正常利用，那我们就可以返回-1；
处理完特殊情况后，接下来我们就需要按照前面的思路进行实现了：
- 定义三个整型变量x/y/z作为指向字符串的指针分别用来记录主串与模式串的下标；
- 通过循环语句完成对主串与模式串元素的访问；
- 通过y与z所记录的下标对应的元素进行字符匹配：
- 匹配成功时，继续向后访问；
- 匹配失败时，先移动x指向的对象，再移动y和z指向的对象，此时
y=x,z=0；
- 循环的判断条件以主串与模式串的串长来共同控制；
- 结束循环后以指向模式串的指针z所对应的元素作为函数返回值的依据：
- 当z指向的元素为
'\0'，说明模式串中的所有元素都成功完成了匹配，此时返回x； - 当z指向的元素不是
'\0'则表示主串中没有找到与模式串相匹配的子串，此时返回-1；
- 当z指向的元素为
完整代码如下所示：
//朴素模式匹配算法
int Index(SString S, char* T) {
if (!T || strlen(T) == 0)
return -1;
int x = 0, y = 0, z = 0;//记录下标的指针
for (x, y, z; S.ch[y] && T[z];) {
if (S.ch[y] == T[z]) {
//当匹配成功时，继续往后匹配
y++;
z++;
}
else {
//当匹配失败时
x++;//找到下一个子串的首元素，并记录对应下标
y = x;//回到子串首元素
z = 0;//回到模式串首元素
}
}
return T[z] ? -1 : x;//通过z指向的模式串所对应的元素进行判断
//ASCII码值为0，则三目操作符的值为x
//ASCII码值不为0，则三目操作符的值为-1
}
2.2.5 代码测试
现在我们已经完成了代码的编写，接下来就来进行一些简单的测试，如下所示：
可以看到，此时咱们的朴素模式匹配算法就很好的完成了。
2.2.6 代码展示
下面附上朴素模式匹配与测试的完整代码：
string.h文件
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
//定长顺序存储
#define MAXSIZE 255//最大串长
typedef struct StackString {
char ch[MAXSIZE];//存储字符的数组
int length;//当前串长
}SString;//重命名后的数据类型名
test.c文件
#include "string.h"
//朴素模式匹配算法
int Index(SString S, char* T) {
if (!T || strlen(T) == 0)
return -1;
int x = 0, y = 0, z = 0;//记录下标的指针
for (x, y, z; S.ch[y] && T[z];) {
if (S.ch[y] == T[z]) {
//当匹配成功时，继续往后匹配
y++;
z++;
}
else {
//当匹配失败时
x++;//找到下一个子串的首元素，并记录对应下标
y = x;//回到子串首元素
z = 0;//回到模式串首元素
}
}
return T[z] ? -1 : x;//通过z指向的模式串所对应的元素进行判断
//ASCII码值为0，则三目操作符的值为x
//ASCII码值不为0，则三目操作符的值为-1
}
//朴素模式匹配算法测试
void test3() {
SString S = { 0 };//初始化
for (int i = 0; i < 10; i++) {
scanf("%c", &S.ch[i]);//创建串S
S.length++;//记录串长
}
printf("S.ch = %s\nS.length = %d\n", S.ch, S.length);//打印串S
char ch[5] = { 0 };
while (scanf("%s", ch) == 1) {
int len = Index(S, ch);
printf("len = %d\n", len);
}
}
int main() {
test3();
return 0;
}
有需要的朋友自行提取。
三、朴素模式匹配算法的缺陷
在串的模式匹配中，朴素模式匹配算法并不是最优的模式匹配算法，前面我们就介绍过，它是一种暴力模式匹配算法。
从之前的演示中，大家应该也能感受到，在整个匹配过程中，指向主串的指针y在每一次匹配失败时都会往前回溯，因此，就会出现很多不必要的匹配过程，如下图所示：
正常情况下，模式串中的元素都不相等，那也就说明前面能够一对一匹配的元素肯定与模式串的前一个元素不匹配，在这种情况下，我们通过回溯后，还是要像这样走一遍匹配的流程，很显然，这是很浪费时间的。
如果我们要优化朴素模式匹配算法的话，那我们就需要将这些不必要的匹配过程给优化一下。我们应该怎么优化呢？
相信大家此时还是比较期待具体的优化方案的。别着急，在下一个篇章中，我们将会详细介绍优化后的模式匹配算法——KMP算法。这也是串这个章节的唯一的重难点。
结语
在今天的内容中，我们详细介绍了什么是串的模式匹配——串的模式匹配就是在主串中找到与模式串相匹配的子串。
随后我们也介绍了为什么要有模式匹配算法——是为了不借助于串的其它基本操作而实现串的模式匹配。
紧接着我们详细剖析了朴素模式算法的底层逻辑，并详细介绍了算法实现的具体过程。
最后我们还提出了朴素模式匹配算法存在的缺陷。为了优化朴素模式匹配算法，在下一个篇章中我们将会详细介绍串的唯一的重难点算法——KMP算法。大家记得关注哦！
今天的内容到这里就全部结束了，如果大家喜欢博主的内容，可以点赞、收藏加评论三连支持一下，也可以转发给身边需要的朋友哦！最后感谢各位的支持，咱们下一篇再见！！！
