C語言模擬實現strstr函數的示例代碼
strstr函數介紹
C語言提供瞭字符串匹配函數 strstr 函數,請看文檔簡介。
這個函數是用來匹配 str2 是否包含在 str1 字符串中,如果匹配成功,則返回指向str1中第一個出現的str2的指針,如果str2不是str1的一部分,則返回空指針。
我們不妨舉例說明,請看下面代碼,調用 strstr 函數需要引入string.h頭文件,我們發現,s1字符串中可以找到s2字符串,那麼就返回s1中s2的第一個字符的地址,s1字符串並沒有s3,所以返回空指針。
#include<stdio.h> #include<string.h> int main(){ char* s1 = "abcdefgh"; char* s2 = "def"; char* s3 = "dee"; printf("%s\n",strstr(s1,s2)); //defgh printf("%s\n",strstr(s1,s3)); //(null) return 0; }
BF算法介紹
BF算法,即暴力(Brute Force)算法,BF算法的思想就是str1的第一個字符與str2的第一個字符進行匹配,若相等,則繼續比較str1的第二個字符和 str2的第二個字符;若不相等,則比較str1的第二個字符和str2的第一個字符,依次比較下去,直到得出最後的匹配結果。
BF算法模擬實現strstr函數
用BF算法實現 strstr 函數的思路就是遍歷整個 str1,在內層循環進行判斷,如果str1 和 str2 對應的字符相等且比較的字符在 str2 長度范圍之內, 那麼就比較下一位,當這次循環結束,此時隻有兩種情況,第一種是比較的字符等於 str2 的長度,那麼就代表找到瞭,返回 str2 在 str1 第一個字符地址即可,至於為什麼是 str1 + i – j,請朋友們思考一下就明白瞭。第二種情況是某個字符之間不匹配,那麼 str1 下次匹配的位置為前一個字符位置 + 1,str2 又回到第一個字符開始匹配。直到整個 str1 超出瞭匹配的范圍,代表找不到整個字符串 str2,故返回NULL。
char* my_strstr(char* str1, char* str2){ assert(str1 && str2); int slen = strlen(str1); int sublen = strlen(str2); int i = 0; int j = 0; int count = 0; while(i < slen){ while(str1[i] == str2[j] && j < sublen){ ++i; ++j; } if(j >= sublen){ return str1 + i - j; } ++count; i = count; j = 0; } return NULL; }
KMP算法介紹
KMP算法是一種改進的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人們稱它為克努特—莫裡斯—普拉特操作(簡稱KMP算法)。KMP算法的核心是利用匹配失敗後的信息,盡量減少模式串(str2)與主串(str1)的匹配次數以達到快速匹配的目的。具體實現就是通過一個next數組實現,數組本身包含瞭模式串的局部匹配信息。
KMP算法與BF算法的區別是:主串不會回退,模式串每次也不一定回退到第一個位置上。
具體算法思想可參考:KMP算法講解
KMP算法模擬實現strstr函數
#include<stdio.h> #include<string.h> #include<assert.h> #include<stdlib.h> void get_next(int* next, char* sub){ int len = strlen(sub); next[0] = -1; next[1] = 0; int i = 2; int k = 0; while(i < len){ if(k == -1 || sub[i-1] == sub[k]){ next[i] = ++k; ++i; }else{ k = next[k]; } } } char* my_strstr(char *str1, char * str2){ assert(str1 && str2); int slen = strlen(str1); int sublen = strlen(str2); int* next = (int*)malloc(sizeof(int)*sublen); assert(next); get_next(next,str2); int i = 0; int j = 0; while(i < slen && j < sublen){ if(j == -1 || str1[i] == str2[j]){ ++i; ++j; }else{ j = next[j]; } } if(i >= sublen){ return str1 + i - j; }else{ return NULL; } }
到此這篇關於C語言模擬實現strstr函數的示例代碼的文章就介紹到這瞭,更多相關C語言 strstr函數內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- 一篇文章帶你實現C語言中常用庫函數的模擬
- strlen函數的使用與模擬實現strlen的方法
- C語言字符串旋轉問題的深入講解
- C語言中“不受限制”的字符串函數總結
- 仿寫C語言string.h頭文件檢驗字符串函數