C語言模擬實(shí)現(xiàn)strstr函數(shù)的示例代碼

更新時(shí)間：2022年07月13日 16:34:29 作者：Liquor999

strstr是C語言中的函數(shù)，作用是返回字符串中首次出現(xiàn)子串的地址。本文將用C語言模擬實(shí)現(xiàn)strstr函數(shù)，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下

strstr函數(shù)介紹

C語言提供了字符串匹配函數(shù) strstr 函數(shù)，請(qǐng)看文檔簡(jiǎn)介。

這個(gè)函數(shù)是用來匹配 str2 是否包含在 str1 字符串中，如果匹配成功，則返回指向str1中第一個(gè)出現(xiàn)的str2的指針，如果str2不是str1的一部分，則返回空指針。
我們不妨舉例說明，請(qǐng)看下面代碼，調(diào)用 strstr 函數(shù)需要引入string.h頭文件，我們發(fā)現(xiàn)，s1字符串中可以找到s2字符串，那么就返回s1中s2的第一個(gè)字符的地址，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的第一個(gè)字符與str2的第一個(gè)字符進(jìn)行匹配，若相等，則繼續(xù)比較str1的第二個(gè)字符和 str2的第二個(gè)字符；若不相等，則比較str1的第二個(gè)字符和str2的第一個(gè)字符，依次比較下去，直到得出最后的匹配結(jié)果。

BF算法模擬實(shí)現(xiàn)strstr函數(shù)

用BF算法實(shí)現(xiàn) strstr 函數(shù)的思路就是遍歷整個(gè) str1，在內(nèi)層循環(huán)進(jìn)行判斷，如果str1 和 str2 對(duì)應(yīng)的字符相等且比較的字符在 str2 長(zhǎng)度范圍之內(nèi)，那么就比較下一位，當(dāng)這次循環(huán)結(jié)束，此時(shí)只有兩種情況，第一種是比較的字符等于 str2 的長(zhǎng)度，那么就代表找到了，返回 str2 在 str1 第一個(gè)字符地址即可，至于為什么是 str1 + i - j，請(qǐng)朋友們思考一下就明白了。第二種情況是某個(gè)字符之間不匹配，那么 str1 下次匹配的位置為前一個(gè)字符位置 + 1，str2 又回到第一個(gè)字符開始匹配。直到整個(gè) str1 超出了匹配的范圍，代表找不到整個(gè)字符串 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算法是一種改進(jìn)的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特—莫里斯—普拉特操作（簡(jiǎn)稱KMP算法）。KMP算法的核心是利用匹配失敗后的信息，盡量減少模式串（str2）與主串（str1）的匹配次數(shù)以達(dá)到快速匹配的目的。具體實(shí)現(xiàn)就是通過一個(gè)next數(shù)組實(shí)現(xiàn)，數(shù)組本身包含了模式串的局部匹配信息。

KMP算法與BF算法的區(qū)別是：主串不會(huì)回退，模式串每次也不一定回退到第一個(gè)位置上。

具體算法思想可參考：KMP算法講解

KMP算法模擬實(shí)現(xiàn)strstr函數(shù)

#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;
    }
    
}

到此這篇關(guān)于C語言模擬實(shí)現(xiàn)strstr函數(shù)的示例代碼的文章就介紹到這了,更多相關(guān)C語言 strstr函數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: