一步一步写算法（之字符串查找 中篇）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

    昨天我们编写了简单的字符查找函数。虽然比较简单，但是也算能用。然而，经过我们仔细分析研究一下，这么一个简单的函数还是有改进的空间的。在什么地方改进呢？大家可以慢慢往下看。

    下面的代码是优化前的代码，现在再贴一次，这样分析起来也方便些：

char* strstr(const char* str, char* data)
{
	int index;
	int len;

	if(NULL == str || NULL == str)
		return NULL;

	len = strlen(data);
	while(*str && (int)strlen(str) >= len){
		for(index = 0; index < len; index ++){
			if(str[index] != data[index])
				break;
		}

		if(index == len)
			return (char*) str;

		str++;
	}

	return NULL;
}

int check_length_of_str(const char* str, int len)
{
	int index;

	for(index = 0; index < len; index ++){
		if(‘\0‘ == str[index])
			return 0;
	}

	return 1;
}

char* strstr(const char* str, char* data)
{
	int index;
	int len;

	if(NULL == str || NULL == str)
		return NULL;

	len = strlen(data);
	while(*str && check_length_of_str(str, len)){
		for(index = 0; index < len; index ++){
			if(str[index] != data[index])
				break;
		}

		if(index == len)
			return (char*) str;

		str++;
	}

	return NULL;
}

char* strstr(const char* str, char* data)
{
	int index;
	int len;

	if(NULL == str || NULL == str)
		return NULL;

	len = strlen(data);
	if((int)strlen(str) < len)
		return NULL;

	while(*str){
		for(index = 0; index < len; index ++){
			if(str[index] != data[index])
				break;
		}

		if(index == len)
			return (char*) str;

		if(‘\0‘ == str[len])
			break;

		str++;
	}

	return NULL;
}

（二）、KMP算法

    KMP算法本质上说是为了消除查找中的多余查找步骤。怎么就产生了多余的查找步骤了呢。我们可以用示例说话。假设有下面两个字符串：

    A：  baaaaabcd

    B：  aaaab

    那么这两个查找的时候会发生什么现象呢？我们可以看一下：

/*      1 2 3 4 5 6 7 8 9
*    A: b a a a a a b c d
*    B:   a a a a b
*       1 2 3 4 5 6 7 8 9
*/  

【预告： 下面一篇博客介绍KMP的编写和多核查找算法】