一,strstr函数
原型:
const char * strstr ( const char * str1, const char * str2 );char * strstr ( char * str1, const char * str2 );
strstr是一个字符串匹配函数,在str1中去寻找str2,如果找到,返回str2在str1中第一次出现的起始位置,没找到就返回空。
在C库中strstr的实现也是使用的暴力算法,所以我们此处也是使用暴力算法来模拟实现。
当然关于字符串匹配的问题还有两个比较出名的算法KMP和BM这两个算法不在此文章介绍,后面会出文章介绍这两种算法,注意,暴力算法不一定是比KMP算法地效的,实际应用时暴力算法的效率大多是比KMP要高的。
二,实现思路
先来看一下动图是怎么走的,然后再来解释具体的过程。
- 起始两个指针都指向的是各字符串的起始字符。
- 开始比较,若对应字符不同,仅移动模式串的指针,使其指向下一个字符。
- 若对应字符相同,两指针同时进行++(开始匹配),指向下一个字符。如是在此过程中,又发生了不匹配的情况,那么字串的指针回到字串的起始位置,模式串指针回到开始匹配的下一个位置。
基于上面模式串要记录开始匹配的位置,我们还需要引入一个指针来记录每一次开始匹配的位置,该指针起始时等于模式串指针。当在匹配的过程中发生中断,就需要该指针++后赋值给模式串指针,让其走到开始匹配位置的下一个字符位置。
代码:
#include <stdio.h>
#include <string.h>char* my_strstr(char* str1, const char* str2)
{//暴力匹配算法char* p0 = str1, * p1 = str1;//p0记录p1开始匹配的起始位置, p1模式串const char* p2 = str2;//字串while (*p1 != '\0'){while (*p1 == *p2 && *p2 != '\0'){p1++;p2++;}if (*p2 == '\0')//匹配成功,返回位置return p0;p1 = ++p0;p2 = str2;}return 0;
}
int main()
{char arr[] = { "caaabcdefgabf" };char* ret = my_strstr(arr, "aab");printf("%s\n", ret);return 0;
}
运行结果:
如有不足,欢迎补充OvO!