【 聲明:版權所有,歡迎轉載,請勿用於商業用途。 聯系信箱: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算法本質上說是為了消除查找中的多余查找步驟。怎麼就產生了多余的查找步驟了呢。我們可以用示例說話。假設有下面兩個字符串:
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
*/
/* 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
*/ 我們發現B和A在從第2個元素開始比較的時候,發現最後一個元素是不同的,A的第6個元素是a,而B的第5個元素是b。按照普通字符串查找的算法,那麼下面A會繼續向右移動一位,但是事實上2-5的字符我們都已經比較過了,而且2-5這4個元素正好和B的前4個元素對應。這個時候B應該用最後一位元素和A的第7位元素比較即可。如果這個計算步驟能省下,查找的速度不就能提高了嗎?