一步一步寫算法（之字符串查找 下篇）

【 聲明：版權所有，歡迎轉載，請勿用於商業用途。  聯系信箱：feixiaoxing @163.com】

    前面我們談到了KMP算法，但是講的還不是很詳細。今天我們可以把這個問題講的稍微詳細一點。假設在字符串A中尋找字符串B，其中字符串B的長度為n，字符串A的長度遠大於n，在此我們先忽略。

    假設現在開始在字符串A中查找，並且假設雙方在第p個字符的時候發現查找出錯了，也就是下面的情況：

/*      
*    A: A1 A2 A3 A4 ... Ap ............
*    B: B1 B2 B3 B4 ... Bp ...Bn 
*                       (p)        
*/     
/*     
*    A: A1 A2 A3 A4 ... Ap ............
*    B: B1 B2 B3 B4 ... Bp ...Bn
*                       (p)       
*/    

    那麼這時候，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); 
} 
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);
}

    當然，上面當然都是為了計算在索引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; 
} 
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;
}
    可能朋友們看到了，上面的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; 
} 
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;
}

（三）、多核查找

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

typedef struct _STRING_PART 
{ 
    char * str; 
    int len; 
}STRING_PART; 
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)); 
} 
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));
}    分好之後，就可以開始並行運算了。

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]; 
} 
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];
}注意事項：

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

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