大家好,又见面了,我是你们的朋友全栈君。
推荐一篇讲解KMP算法的文章–阮一峰http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html
推荐一篇讲解Boyer-Moore算法的文章–阮一峰http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
strstr函数用于在字符串中查找字串,本篇博客我们主要讲解一下它的实现过程。以我自己为例,刚开始写strstr函数的实现还是漏洞百出的。下面就记录一下我当时的思考过程。
strstr在进行字串查找时,如果找到,则返回字串在源字符串中第一次出现的位置;如果没有找到,则返回NULL。下面我们逐步来看可能出现的各种情况。
(1)源串:abcd
字串:bc
思路:让str和sub两个指针分别指向源串和字串的起始位置,然后进行比较,如果相等,则str和sub指针同时向后移,在比较下一个字符;如果不相等,则另str指针向后移,然后再进行比较。比较结束的时间点:str和sub指针当中有任意一个已经到达了字符串末尾‘\0’处。如果sub到达‘\0’,则说明两个字符串已经相等。
则不难写出以下代码:
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
while (*str != '\0'&&*sub != '\0')
{
if (*str == *sub)
{
str++;
sub++;
}
else
{
str++;
}
}
if (*sub == '\0')
{
return ?;
}
return NULL;
}
int main()
{
char str[] = "abcd";
char *p ;
p = Strstr(str, "bc");
printf("%s", p);
system("pause");
return 0;
}
注意看“return ?”这里,按照上面所举的例子,对应的逻辑,我们已经遍历到了字串的\0处,判断出来字串bc在对应源串的1(这里见图解)处,那么问题来了?虽然已经找到了字串对应的位置,但是如何返回呢?str指针已经移动到了3(即d)的位置处。很明显无法在找到字串第一次出现的位置了。
这个问题给我们的启示是:在两个指针不断移动进行比较期间,一定要保存下匹配的位置。那么如何保存呢?显然还需要定义另一个指针。回顾我们一开始的思路:一直都是拿原生的两个指针进行移动比较。所以对于这个问题,显然仅仅原生指针比较是不可行的。
想明白问题所在的点后,我们对代码进行修改(这里我们又定义了一个start指针,用于保存第一次匹配成功时记录位置)
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*start = str;//start指针保存匹配成功的位置
while (*str != '\0'&&*sub != '\0')
{
if (*str == *sub)
{
str++;
sub++;
}
else
{
str++;
start = str;
}
}
if (*sub == '\0')
{
return start;
}
return NULL;
}
运行结果:
但是如果例题改为在abbcd中查找bc,则结果就不正确了
char str[] = "abbcd";
char *p ;
p = Strstr(str, "bc");
printf("%s", p);
运行结果:
我们来分析一下原因,当两个指针都走到2时,b与c不匹配,这时,str指针继续往后走,即走到3的位置,然后赋给了start指针,这时str和sub指针都指向了c;最后一步,sub指针已经到达‘\0’,循环退出,所以最后输出的就是cd。本次的出错点就在:当str走到第二个b时(2的位置),发现与c不匹配,那么那一次比较时,就要重新字串的起始位置处进行比较,而不是直接往后走。
于是我们尝试着再把代码做修改:
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*start = str;//start指针保存匹配成功的位置
const char*sub_p = sub;//另sub_p遍历字串
while (*str != '\0'&&*sub_p != '\0')
{
if (*str == *sub_p)
{
str++;
sub_p++;
}
else
{
str++;
start = str;
sub_p = sub;//回到字串的起始位置进行重新匹配
}
}
if (*sub_p == '\0')
{
return start;
}
return NULL;
}
结果:
结果还是错误,原因在于:当str走到2(b)时,sub_p也走到2(c)时,发现不匹配,这时本应该sub_p回到子串起始位置处,str继续从2(b)的位置处开始比较。但是由于else语句中str先++了,所以str直接指向了3(c),随后sub_p指向初始位置b,所以后边再怎么比较也不可能有匹配的字符串。
综上:我们用了很长的篇幅去分析代码每次出现的错误,每分析出来错误的点进行修改总是“当前问题解决了,但是又带来了新问题”,说明之前的代码框架有问题,这时不如重新构建一下代码框架,换个思路。
通过上面众多例子的分析:搞清楚了两个最重要的问题:
(1)匹配成功时,最后返回的是字串第一次出现的位置。而两个指针进行比较时都是依次向后移动的,只有字串的指针到达\0才说明匹配成功,那这时指针已经指向了后面的字符,怎么返回匹配成功的第一个字符的位置?所以就需要再定义一个指针来保存这个位置
(2)基本的逻辑我们已经知道,当连个指针指向的字符相同时,指针都向后移,再比较下一个字符;当不同时,源字符串的指针向后移一位,进行比较。注意,这时比较就要从字串的起始处重新开始比较了。
综上,整理一下逻辑,如图所示–>
最终代码:
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*str_p = str;//sub_p指针遍历源字符串进行比较
const char*start = str;//start指针保存匹配成功的位置
const char*sub_p = sub;//sub_p遍历子串进行比较
while (*start != '\0')
{
str_p = start;
sub_p = sub;//每次匹配不成功时都要从子串的起始处重新比较
while (*str_p != '\0'&&*sub_p != '\0')
{
if (*str_p == *sub_p)
{
str_p++;
sub_p++;
}
else
{
break;
}
}
if (*sub_p == '\0')
{
return start;
}
start++;//当前位置开始匹配不成功时,从下一个位置开始尝试匹配
}
return NULL;
}
下面的也可以
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
char*Strstr(const char*str, const char*sub)
{
assert(str);
assert(sub);
const char*str_p = str;//str_p真正向后走
const char*start = str_p;//start用来指向起始位置
const char*sub_p = sub;
while (*start)//外层循环只是决定了从什么时候开始
{
str_p = start;
sub_p = sub;
//内层循环才是真正比较
while (*str_p&&*sub_p&&*str_p == *sub_p)
{
str_p++;
sub_p++;
}
//只要两个字符不相等就停下来,或者有一个已经到达\0就停下来
//*sub_p=='\0'说明比较成功了,这时候返回起始比较位置,而起始比较位置在start当中保存着
if (*sub_p == '\0')
{
return start;
}
start++;
}
return NULL;
}
int main()
{
char str[] = "abbbbcdef";
char *p ;
p = strstr(str, "bbc");
printf("%s", p);
system("pause");
return 0;
}
运行结果:
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/152983.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...