C语言模拟实现strstr函数的代码怎么写(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>intmain(){char*s1="abcdefgh";char*s2="def";char*s3="dee";printf("%s\n",strstr(s1,s2));//defghprintf("%s\n",strstr(s1,s3));//(null)return0;}

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);intslen=strlen(str1);intsublen=strlen(str2);inti=0;intj=0;intcount=0;while(i<slen){while(str1[i]==str2[j]&&j<sublen){++i;++j;}if(j>=sublen){returnstr1+i-j;}++count;i=count;j=0;}returnNULL;}

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>voidget_next(int*next,char*sub){intlen=strlen(sub);next[0]=-1;next[1]=0;inti=2;intk=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);intslen=strlen(str1);intsublen=strlen(str2);int*next=(int*)malloc(sizeof(int)*sublen);assert(next);get_next(next,str2);inti=0;intj=0;while(i<slen&&j<sublen){if(j==-1||str1[i]==str2[j]){++i;++j;}else{j=next[j];}}if(i>=sublen){returnstr1+i-j;}else{returnNULL;}}