"暴力"字符匹配算法的C语言实现
共 5381字，需浏览 11分钟
·
2021-03-02 23:07
1、聊一聊
今天跟大家分享的这个曲子一般是在天气预报和英语试听中出现，不信你听一听绝对有种似曾相识感觉。
本篇文章主要是为讲解高效字符匹配算法的一则预告文，跟大家讲讲暴力字符匹配算法以及匹配算法在通信中如何使用。
2、暴力匹配算法介绍
1
可是理论算法研究和实际应用还是有一定的脱节，往往一些高级的算法并没有得到广泛的工程应用，面对目前快节奏的功能开发形成了 : "算法的思想越简单，实际应用的效果越好"的思想。
所以bug菌从最简单的匹配算法跟大家讲起，对一些匹配性能要求不高的项目还是非常奏效的。
2
暴力字符匹配算法的实现原理还是非常简单的，从第一个字符开始进行匹配，如果匹配不成功，移动到下一个字节重新开始逐个匹配，其实现过程如下图所示:
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实现，供大家欣赏一下即可:
3
在平时的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、暴力匹配在通信中的使用
1
一般都会把数据接收以后放入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}
对于以后跟大家介绍的高效字符匹配算法经过类似修改以后均可以用到字节流传递过程中来。
5、最后小结
暴力字符串匹配算法就说这么多了。
