C++算法之字符串查找

jopen 9年前發布 | 2K 次閱讀 C/C++ 算法

字符串運算是我們開發軟件的基本功，其中比較常用的功能有字符串長度的求解、字符串的比較、字符串的拷貝、字符串的upper等等。另外一個經常使用但是卻被我們忽視的功能就是字符串的查找。word里面有字符串查找、notepad里面有字符串查找、winxp里面也有系統自帶的字符串的查找，所以編寫屬于自己的字符串查找一方面可以提高自己的自信心，另外一方面在某些情況下可以提高軟件的運行效率。下面我們就三個方面討論一下字符串的查找方法：
1）基本字符串查找
2）KMP查找
3）多核cpu下的字符串查找     （一）、首先介紹一下普通的字符串查找方法：
    a）指針是否為空，否則返回
    b）判斷str是否為‘\0’，判斷剩下來的字符串長度是否>=模板字符串的長度，只有一個不符合，函數結束運行
    c）依次比較字符串和模板字符串的內容，如果全部符合，返回；只要一個不符合，break跳出，str加1，轉b）
    那么算法應該怎么寫呢？朋友們可以自己先書寫一下，即使在紙上寫也可以。

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;  

}

</pre>     為了說明代碼的正確性，我們可以編寫幾個測試用例測試一下。
void test()

{

    assert(NULL == strstr(NULL, "china"));

    assert(NULL == strstr("hello, world", "china"));

    assert(NULL != strstr("hello, china", "china"));

}
</pre>  前面我們編寫了簡單的字符查找函數。雖然比較簡單，但是也算能用。然而，經過我們仔細分析研究一下，這么一個簡單的函數還是有改進的空間的。在什么地方改進呢？大家可以慢慢往下看。

     下面的代碼是優化前的代碼，現在再貼一次，這樣分析起來也方便些：
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;  

}

</pre>     不知道朋友們發現沒有，原來的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;  

}

</pre>     上面的代碼很好地解決了長度判斷的問題，這樣一來每次比較的長度很短，只要判斷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;  

}
</pre>     和上面第一次的優化不同，我們在進入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 
/

</pre>     我們發現B和A在從第2個元素開始比較的時候，發現最后一個元素是不同的，A的第6個元素是a，而B的第5個元素是b。按照普通字符串查找的算法，那么下面A會繼續向右移動一位，但是事實上2-5的字符我們都已經比較過了，而且2-5這4個元素正好和B的前4個元素對應。這個時候B應該用最后一位元素和A的第7位元素比較即可。如果這個計算步驟能省下，查找的速度不就能提高了嗎？ 
前面我們談到了KMP算法，但是講的還不是很詳細。今天我們可以把這個問題講的稍微詳細一點。假設在字符串A中尋找字符串B，其中字符串B的長度為n，字符串A的長度遠大于n，在此我們先忽略。
假設現在開始在字符串A中查找，并且假設雙方在第p個字符的時候發現查找出錯了，也就是下面的情況：
--}
/       
A: A1 A2 A3 A4 ... Ap ............ 
B: B1 B2 B3 B4 ... Bp ...Bn  
(p)

*/      

</pre>     那么這時候，A有什么選擇呢？它可以左移1位，用A2~A(p-1)比較B1~B(p-2)，然后再用A(p)~A(n+1)比較B(p-1)~B(n)位；或者左移2位，用A3~A(p-1)比較B1~B(p-3)，然后再用A(p)~A(n+2)比較B(p-2)~B(n)位； 依次類推，直到左移（p-2）位，用A(p-1)比較B(1)，然后再用A(p)~A(p+n-2)比較B(2)~B(n)位。

     不知道細心的朋友們發現什么規律沒？因為A和B在前面（p-1）個數據是相等的，所以上面的計算其實可以這樣看：用A2~A(p-1)比較B1~B(p-2)，實際上就是B2~B(p-1)比較B1~B(p-2)； 用A3~A(p-1)比較B1~B(p-3)，實際上就是B3~B(p-1)比較B1~B(p-3)；最后直到B(p)和B(1)兩者相比較。既然這些數據都是B自身的數據，所以當然我們可以提前把這些結果都算出來的。

     那么這么多的選擇，我們應該左移多少位呢？

     其實判斷很簡單。假設我們左移1位，發現A2~A(p-1)的結果和B1~B(p-2)是一致的，那么兩者可以直接從第(p-1)位開始比較了； 如果不成功呢，那么只能左移2位，并判斷A2~A(p-1)和B1~B(p-2)的比較結果了，......，這樣以此類推進行比較。如果不幸發現所有的數據都不能比較成功呢，那么只能從頭再來，從第1位數據依次進行比較了。

     不知道講清楚了沒，還沒有明白的朋友可以看看下面的代碼：


int calculate_for_special_index(char str[], int index)

{

    int loop;

    int value;

value = 0;  
for(loop = 1; loop < index; loop ++){  
    if(!strncmp(&str[loop], str, (index - loop))){  
        value = index - loop;  
        break;  
    }  
}  

return (value == 0) ? 1 : (index - value);  

}
void calculate_for_max_positon(char str[], int len, int data[])

{

    int index;

for(index = 0; index < len; index++)  
    data[index] = calculate_for_special_index(str, index);  

}

</pre>    當然，上面當然都是為了計算在索引n比較失敗的時候，判斷此時字符應該向左移動多少位。
char strstr_kmp(const char str, char data)

{

    int index;

    int len;

    int value;

    int pData;

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

len = strlen(data);  
pData = (int*)malloc(len * sizeof(int));  
memset(pData, 0, len * sizeof(int));  
calculate_for_max_positon((char*)str, len, pData);  

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

    if(index == len){  
        free(pData);  
        return (char*) str;  
    }  

    value = pData[index];  
    str += value;  

    if(value == 1)  
        index = 0;  
    else  
        index = index -value;  
}  

free(pData);  
return NULL;  

}

</pre>    可能朋友們看到了，上面的strlen又回來了？說明代碼本身還有優化的空間。大家可以自己先試一試。
int check_valid_for_kmp(char str[], int start, int len)

{

    int index;

for(index = start; index < len; index++)  
    if('\0' == str[index])  
        return 0;  
return 1;  

}
char strstr_kmp(const char str, char data)

{

    int index;

    int len;

    int value;

    int pData;

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

len = strlen(data);  
pData = (int*)malloc(len * sizeof(int));  
memset(pData, 0, len * sizeof(int));  
calculate_for_max_positon((char*)str, len, pData);  

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

    if(index == len){  
        free(pData);  
        return (char*) str;  
    }  

    value = pData[index];  
    str += value;  

    if(value == 1)  
        index = 0;  
    else  
        index = index -value;  
}  

free(pData);  
return NULL;  

}

</pre> 

 （三）、多核查找

     多核查找其實不新鮮，就是把查找分成多份，不同的查找過程在不同的核上面完成。舉例來說，我們現在使用的cpu一般是雙核cpu，那么我們可以把待查找的字符分成兩份，這樣兩份查找就可以分別在兩個核上面同時進行了。具體怎么做呢，其實不復雜。首先我們要定義一個數據結構：


typedef struct _STRING_PART  
{  
    char * str;  
    int len;  
}STRING_PART;  
     接著，我們要做的就是把字符串分成兩等分，分別運算起始地址和長度。
void set_value_for_string_part(char str[], int len, STRING_PART part[])

{

    char* middle = str + (len >> 1);

while(' ' != *middle)  
    middle --;  

part[0].str = str;  
part[0].len = middle - (str -1);  

part[1].str = middle + 1;  
part[1].len = len - (middle - (str - 1));  

}
</pre>     分好之后，就可以開始并行運算了。
char strstr_omp(char str[], char data[])

{

    int index;

    STRING_PART part[2] = {0};

    char result[2] = {0};

    int len = strlen(str);

set_value_for_string_part(str, len, part);  


pragma omp parellel for

for(index = 0; index < 2; index ++)  
    result[index] = strstr(part[index].str, part[index].len, data);  

if(NULL == result[0] && NULL == result[1])  
    return NULL;  

return (NULL != result[0]) ? result[0] : result[1];  

}
</pre> 注意事項：

     （1）這里omp宏要在VS2005或者更高的版本上面才能運行，同時需要添加頭文件#include，打開openmp的開關；

     （2）這里調用的strstr函數第2個參數是目標字符串的長度，和我們前面介紹的普通查找函數稍微不一樣，前面的函數不能直接使用，但稍作改變即可。

本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/code/view/1434359971833

C/C++ 算法

C++算法之字符串查找

pragma omp parellel for

相關代碼

相關文檔

相關經驗

目錄