【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：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位元素比較即可。如果這個計算步驟能省下，查找的速度不就能提高了嗎？
