一步一步写算法（之字符串查找 中篇）
【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：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;
}
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;
} 不知道朋友们发现没有，原来的while条件中有一个很费时的操作。那就是每次str移动的时候，都需要判断str的长度大小。如果str的长度远大于data的长度，那么计算str长度的时间是相当可观的。
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;
}
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;
} 上面的代码很好地解决了长度判断的问题，这样一来每次比较的长度很短，只要判断len的大小字符长度即可。但是，我们还不是很满足，如果两者不比较岂不更好。那么，有没有这个可能？我们发现，如果str在每次比较不成功的时候，就会自己递增一位。那么我们只要判断这一位是不是‘\0’不就可以了吗？所以说，我们的代码还可以写成下面的形式。
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;
}
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;
} 和上面第一次的优化不同，我们在进入while之前会判断两者的长度区别，但是经过第一次判断之后，我们就再也不用判断了，因为接下来我们只要判第n个元素是否为‘\0’即可，原来的n-1个元素我们已经判断过了，肯定是合法的元素。为什么呢？大家可以好好想想。
（二）、KMP算法
KMP算法本质上说
补充：软件开发 , C语言 ,
