C语言模拟实现strstr函数的示例代码

目录

strstr函数介绍

C语言提供了字符串匹配函数>

这个函数是用来匹配 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>

BF算法模拟实现strstr函数

用BF算法实现>

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函数内容请搜索易采站长站以前的文章或继续浏览下面的相关文章希望大家以后多多支持易采站长站！