【算法】"暴力"字符匹配算法的C语言实现

Original bug菌最后一个bug 2022-07-15

收录于合集 #原创单片机进阶必备 85个

1、聊一聊

今天跟大家分享的这个曲子一般是在天气预报和英语试听中出现，不信你听一听绝对有种似曾相识感觉。

本篇文章主要是为讲解高效字符匹配算法的一则预告文，跟大家讲讲暴力字符匹配算法以及匹配算法在通信中如何使用。

2、暴力匹配算法介绍

聊聊字符匹配算法

bug菌所说的暴力匹配算法就是C标准库函数strstr()，如果你还没有使用过或者没有听到过这个函数，那就有点......。

字符匹配算法的应用其实是非常广泛的，小到信息的检索，大到网络安全监测，一种高效的字符匹配算法能够大大改善性能，所以目前对字符匹配算法的理论研究也是在一直进行着。

可是理论算法研究和实际应用还是有一定的脱节，往往一些高级的算法并没有得到广泛的工程应用，面对目前快节奏的功能开发形成了 : "算法的思想越简单，实际应用的效果越好"的思想。

所以bug菌从最简单的匹配算法跟大家讲起，对一些匹配性能要求不高的项目还是非常奏效的。

暴力字符匹配的实现原理

暴力字符匹配算法的实现原理还是非常简单的，从第一个字符开始进行匹配，如果匹配不成功，移动到下一个字节重新开始逐个匹配，其实现过程如下图所示:

看似该算法实现得理所当然，不过对于部分情况其效率相对比较低下,看看如下情况:

上图是按照暴力字符匹配算法进行的匹配过程，我们如果仔细分析一下可以发现第二步的比较是必然不会成立的，因为第一步abab都匹配成功了，移动一位肯定是匹配不成功的，所以这样就增加了算法在时间上的复杂度，有没有更优的算法解决这个问题? 答案肯定是有的，下篇文章跟大家详细介绍。

不过暴力匹配算法的好处就是理解上非常的简单，也可以说比较呆吧，往往简单的东西更加容易让大家接受，并且应用在实际的项目中，除非特别是对匹配效率比较敏感的项目。

3、暴力匹配的C代码实现

参考实现1

strstr()既然是标准C库函数，那么稍微大一点的软件源码都会有相应的实现，一般都写得比较精炼的，那么看看Linux源码咯,于是截图了其实现函数供大家参考:

对于linux里面的strstr实现比较清晰，获得两个字符串的长度，然后逐位比较模式串与主串的长度，如果匹配返回成功，否则把主串指针移动一位继续循环比较。

上面的代码看似比较简单，如果真的徒手写一个你还真不一定考虑得那么全面，比如下面几个细节：

strstr函数的形参均采用const char *的形式，这就回到了老生常谈的const的用法了<参考:一文搞定C语言const关键字>，即不允许函数内部修改指针所指向的地址数据内容，对数据起到一定的保护作用。
memcmp采用const void *<参考:【C进阶】同事用void把我给秀翻了！>，使得函数更加通用。
内部for里面采用逗号表达式<参考:【C进阶】听说用 “ 逗号表达式 ” 仅仅为了秀技？> ，程序更加紧凑、精炼。
以及size_t是什么东西，为什么使用它？

参考实现2

然而bug菌在翻阅一些代码中发现，还有strstr采用汇编来实现的，毕竟库函数相对比较固定，其主要是为了能够加快运算速度，下面是X86的strstr实现，供大家欣赏一下即可:

简化版实现

在平时的mcu开发中，bug菌不太喜欢调用库函数，就像上面的实现，一个不太复杂的程序里面进行了较多函数的嵌套，可能在性能强悍的芯片上倒问题不大，不过对于一些频繁使用该函数的中低端芯片来说性能上还是会有一定的损失的。

所谓”高端秀功能，低端秀成本”，所以来个常用的简化版本，供大家参考:

 1#include <stdio.h>
 2
 3char* pChild = "123";
 4char* pParent = "456789123789456123" ;
 5
 6char* strstr(const char*s1,const char*s2)
 7{
 8    int n;
 9    if(*s2)
10    {
11        while(*s1)
12        {
13            for(n=0;*(s1+n)==*(s2+n);n++)
14            {
15                if(!*(s2+n+1))
16                    return(char*)s1;
17            }
18            s1++;
19        }
20        return NULL;
21    }
22    else
23        return (char*)s1;
24}
25
26int main(int argc, char *argv[]) {
27
28    printf("  %d\n",strstr(pParent,pChild) - pParent);
29    printf("公众号:最后一个bug\n");
30    return 0;
31}

4、暴力匹配在通信中的使用

应用

如果仅仅只是匹配字符或者关键字等等，上面的代码可以直接拿来使用，在有些字节流的通信协议中都会存在帧头和帧尾的匹配问题，字符的匹配和帧头尾匹配思路上是一致的，所以仅仅只需要对函数进行改造以适应字节数据查找即可。

一般都会把数据接收以后放入buff中，然后通过匹配算法查找帧头，帧尾，通过定位帧头进而确定通信格式和数据完整性分析等。所以这里把字符匹配算法修改一下，获得如下代码:

 1typedef unsigned char uint8_t;
 2typedef unsigned int  uint16_t;
 3
 4#include <stdio.h>
 5
 6uint8_t Head[3] = {0x01,0x02,0x03};
 7uint8_t Buff[10] = {0x01,0x01,0x01,0x02,0x02,
 8                    0x01,0x02,0x03,0x02,0x02};
 9
10uint8_t* Bytestrstr(const uint8_t *s1 ,uint16_t len1,uint8_t*s2,uint16_t len2)
11{
12    uint16_t n;
13    uint16_t cnt;
14
15    if(*s2 || len2) 
16    {
17        for(cnt = 0;cnt < len1;cnt ++)
18        {
19            for(n=0;*(s1+n)==*(s2+n);n++)
20            {
21                if(n == (len2-1))
22                    return(uint8_t*)s1;
23            }
24            s1++;
25        }
26        return NULL;
27    }
28    else
29        return (char*)s1;
30}
31
32int main(int argc, char *argv[]) {
33
34    printf("  %d\n",Bytestrstr(Buff,10,Head,3) - Buff);
35    printf("公众号:最后一个bug\n");
36    return 0;
37}