模拟实现strstr函数

大家好，又见面了，我是你们的朋友全栈君。

推荐一篇讲解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;
}

运行结果：