昨天我們編寫(xiě)了簡(jiǎn)單的字符查找函數(shù)。雖然比較簡(jiǎn)單，但是也算能用。然而，經(jīng)過(guò)我們仔細(xì)分析研究一下，這么一個(gè)簡(jiǎn)單的函數(shù)還是有改進(jìn)的空間的。在什么地方改進(jìn)呢？大家可以慢慢往下看。

下面的代碼是優(yōu)化前的代碼，現(xiàn)在再貼一次，這樣分析起來(lái)也方便些：

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;  
}  

不知道朋友們發(fā)現(xiàn)沒(méi)有，原來(lái)的while條件中有一個(gè)很費(fèi)時(shí)的操作。那就是每次str移動(dòng)的時(shí)候，都需要判斷str的長(zhǎng)度大小。如果str的長(zhǎng)度遠(yuǎn)大于data的長(zhǎng)度，那么計(jì)算str長(zhǎng)度的時(shí)間是相當(dāng)可觀的。

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;  
}  

上面的代碼很好地解決了長(zhǎng)度判斷的問(wèn)題，這樣一來(lái)每次比較的長(zhǎng)度很短，只要判斷l(xiāng)en的大小字符長(zhǎng)度即可。但是，我們還不是很滿足，如果兩者不比較豈不更好。那么，有沒(méi)有這個(gè)可能？我們發(fā)現(xiàn)，如果str在每次比較不成功的時(shí)候，就會(huì)自己遞增一位。那么我們只要判斷這一位是不是‘\0’不就可以了嗎？所以說(shuō)，我們的代碼還可以寫(xiě)成下面的形式。

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;  
}  

和上面第一次的優(yōu)化不同，我們?cè)谶M(jìn)入while之前會(huì)判斷兩者的長(zhǎng)度區(qū)別，但是經(jīng)過(guò)第一次判斷之后，我們就再也不用判斷了，因?yàn)榻酉聛?lái)我們只要判第n個(gè)元素是否為‘\0’即可，原來(lái)的n-1個(gè)元素我們已經(jīng)判斷過(guò)了，肯定是合法的元素。為什么呢？大家可以好好想想。

（二）、KMP算法 KMP算法本質(zhì)上說(shuō)是為了消除查找中的多余查找步驟。怎么就產(chǎn)生了多余的查找步驟了呢。我們可以用示例說(shuō)話。假設(shè)有下面兩個(gè)字符串：

A： baaaaabcd

B： aaaab

那么這兩個(gè)查找的時(shí)候會(huì)發(fā)生什么現(xiàn)象呢？我們可以看一下：

/*      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 
*/    

我們發(fā)現(xiàn)B和A在從第2個(gè)元素開(kāi)始比較的時(shí)候，發(fā)現(xiàn)最后一個(gè)元素是不同的，A的第6個(gè)元素是a，而B(niǎo)的第5個(gè)元素是b。按照普通字符串查找的算法，那么下面A會(huì)繼續(xù)向右移動(dòng)一位，但是事實(shí)上2-5的字符我們都已經(jīng)比較過(guò)了，而且2-5這4個(gè)元素正好和B的前4個(gè)元素對(duì)應(yīng)。這個(gè)時(shí)候B應(yīng)該用最后一位元素和A的第7位元素比較即可。如果這個(gè)計(jì)算步驟能省下，查找的速度不就能提高了嗎？