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; } 为了说明代码的正确性，我们可以编写几个测试用例测试一下。 void test() { assert(NULL == strstr(NULL, "china")); assert(NULL == strstr("hello, world", "china")); assert(NULL != strstr("hello, china", "china")); } 前面我们编写了简单的字符查找函数。虽然比较简单，但是也算能用。然而，经过我们仔细分析研究一下，这么一个简单的函数还是有改进的空间的。在什么地方改进呢？大家可以慢慢往下看。 下面的代码是优化前的代码，现在再贴一次，这样分析起来也方便些：
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; } 上面的代码很好地解决了长度判断的问题，这样一来每次比较的长度很短，只要判断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; } 和上面第一次的优化不同，我们在进入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 */我们发现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) */那么这时候，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); } 当然，上面当然都是为了计算在索引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; } 可能朋友们看到了，上面的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; } （三）、多核查找
多核查找其实不新鲜，就是把查找分成多份，不同的查找过程在不同的核上面完成。举例来说，我们现在使用的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)); } 分好之后，就可以开始并行运算了。 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，打开openmp的开关；
（2）这里调用的strstr函数第2个参数是目标字符串的长度，和我们前面介绍的普通查找函数稍微不一样，前面的函数不能直接使用，但稍作改变即可。