1、聊一聊

今天跟大家分享的這個曲子一般是在天氣預報和英語試聽中出現，不信你聽一聽絕對有種似曾相識感覺。

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

2、暴力匹配算法介紹

1

聊聊字符匹配算法

bug菌所說的暴力匹配算法就是C標準庫函數strstr()，如果你還沒有使用過或者沒有聽到過這個函數，那就有點......。

字符匹配算法的應用其實是非常廣泛的，小到信息的檢索，大到網絡安全監測，一種高效的字符匹配算法能夠大大改善性能，所以目前對字符匹配算法的理論研究也是在一直進行著。

可是理論算法研究和實際應用還是有一定的脫節，往往一些高級的算法并沒有得到廣泛的工程應用，面對目前快節奏的功能開發形成了?: "算法的思想越簡單，實際應用的效果越好"的思想。

所以bug菌從最簡單的匹配算法跟大家講起，對一些匹配性能要求不高的項目還是非常奏效的。

2

暴力字符匹配的實現原理

暴力字符匹配算法的實現原理還是非常簡單的，從第一個字符開始進行匹配，如果匹配不成功，移動到下一個字節重新開始逐個匹配，其實現過程如下圖所示:

看似該算法實現得理所當然，不過對于部分情況其效率相對比較低下,看看如下情況:

上圖是按照暴力字符匹配算法進行的匹配過程，我們如果仔細分析一下可以發現第二步的比較是必然不會成立的，因為第一步abab都匹配成功了，移動一位肯定是匹配不成功的，所以這樣就增加了算法在時間上的復雜度，有沒有更優的算法解決這個問題? 答案肯定是有的，下篇文章跟大家詳細介紹。

不過暴力匹配算法的好處就是理解上非常的簡單，也可以說比較呆吧，往往簡單的東西更加容易讓大家接受，并且應用在實際的項目中，除非特別是對匹配效率比較敏感的項目。

3、暴力匹配的C代碼實現

1

參考實現1

strstr()既然是標準C庫函數，那么稍微大一點的軟件源碼都會有相應的實現，一般都寫得比較精煉的，那么看看Linux源碼咯,于是截圖了其實現函數供大家參考:

對于linux里面的strstr實現比較清晰，獲得兩個字符串的長度，然后逐位比較模式串與主串的長度，如果匹配返回成功，否則把主串指針移動一位繼續循環比較。

上面的代碼看似比較簡單，如果真的徒手寫一個你還真不一定考慮得那么全面，比如下面幾個細節：

• strstr函數的形參均采用const char *的形式，這就回到了老生常談的const的用法了<參考:一文搞定C語言const關鍵字>，即不允許函數內部修改指針所指向的地址數據內容，對數據起到一定的保護作用。

• memcmp采用const void *<參考:【C進階】同事用void把我給秀翻了！>，使得函數更加通用。
  

• 內部for里面采用逗號表達式<參考:【C進階】聽說用 “ 逗號表達式 ” 僅僅為了秀技？> ，程序更加緊湊、精煉。
  

• 以及size_t是什么東西，為什么使用它？

2

參考實現2

然而bug菌在翻閱一些代碼中發現，還有strstr采用匯編來實現的，畢竟庫函數相對比較固定，其主要是為了能夠加快運算速度，下面是X86的strstr實現，供大家欣賞一下即可:

3

簡化版實現

在平時的mcu開發中，bug菌不太喜歡調用庫函數，就像上面的實現，一個不太復雜的程序里面進行了較多函數的嵌套，可能在性能強悍的芯片上倒問題不大，不過對于一些頻繁使用該函數的中低端芯片來說性能上還是會有一定的損失的。

所謂”高端秀功能，低端秀成本”，所以來個常用的簡化版本，供大家參考:

1#include?<stdio.h>23char*?pChild?=?"123";4char*?pParent?=?"456789123789456123"?;56char*?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;34#include?<stdio.h>56uint8_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、最后小結

暴力字符串匹配算法就說這么多了。

---

推薦閱讀：

專輯|Linux文章匯總

專輯|程序人生

專輯|C語言

我的知識小密圈

關注公眾號，后臺回復「1024」獲取學習資料網盤鏈接。

歡迎點贊，關注，轉發，在看，您的每一次鼓勵，我都將銘記于心~

總結

以上是生活随笔為你收集整理的暴力字符匹配算法的C语言实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。