c 算法之字符串查找

《c 算法之字符串查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C++算法之字符串查找字符串运算是我们开发软件的基本功，其中比较常用的功能有字符串长度的求解、字符串的比较、字符串的拷贝、字符串的upper等等。另外一个经常使用但是却被我们忽视的功能就是字符串的查找。word里面有字符串查找、notepad里面有字符串查找、winxp里面也有系统自带的字符串的查找，所以编写属于自己的字符串查找一方面可以提高自己的自信心，另外一方面在某些情况下可以提高软件的运行效率。下面我们就三个方面讨论一下字符串的查找方法： 1）基本字符串查找 2）KMP查找 3）多核cpu下的字符

2、串查找（一）、首先介绍一下普通的字符串查找方法： a）指针是否为空，否则返回 b）判断str是否为‘’，判断剩下来的字符串长度是否=模板字符串的长度，只有一个不符合，函数结束运行 c）依次比较字符串和模板字符串的内容，如果全部符合，返回；只要一个不符合，break跳出，str加1，转b） 那么算法应该怎么写呢？朋友们可以自己先书写一下，即使在纸上写也可以。 char*strstr(constchar*str,char*data) intindex; intlen; if(NULL==str

3、

4、NU

5、LL==str) returnNULL; len=strlen(data); while(*str(int)strlen(str)=len){ for(index=0;indexlen;index++){ if(str[index]!=data[index]) break; if(index==len) return(char*)str; str++; returnNULL; 为了说明代码的正确性，我们可以编写几个测试用例测试一下。 voidtest() assert(NULL==strstr(NUL

6、L,china)); assert(NULL==strstr(hello,world,china)); assert(NULL!=strstr(hello,china,china)); 前面我们编写了简单的字符查找函数。虽然比较简单，但是也算能用。然而，经过我们仔细分析研究一下，这么一个简单的函数还是有改进的空间的。在什么地方改进呢？大家可以慢慢往下看。 下面的代码是优化前的代码，现在再贴一次，这样分析起来也方便些： char*strstr(constchar*str,char*data) intin

7、dex; intlen; if(NULL==str

8、

9、NULL==str) returnNULL; len=strlen(data); while(*str(int)strlen(str)=len){ for(index=0;indexlen;index++){ if(str[index]!=data[index]) break; if(index==len) return(char*)str; str++; returnNULL; 不知道朋友们发现没有，原来的while条件中有一个很费时的操作。那就是

10、每次str移动的时候，都需要判断str的长度大小。如果str的长度远大于data的长度，那么计算str长度的时间是相当可观的。 intcheck_length_of_str(constchar*str,intlen) intindex; for(index=0;indexlen;index++){ if(‘’==str[index]) return0; return1; char*strstr(constchar*str,char*data) intindex; intlen; if(NULL==

11、str

12、

13、NULL==str) returnNULL; len=strlen(data); while(*strcheck_length_of_str(str,len)){ for(index=0;indexlen;index++){ if(str[index]!=data[index]) break; if(index==len) return(char*)str; str++; returnNULL; 上面的代码很好地解决了长度判断的问题，这样一来每次比较的长度很短，只要判断len的大小字符长度即可

14、。但是，我们还不是很满足，如果两者不比较岂不更好。那么，有没有这个可能？我们发现，如果str在每次比较不成功的时候，就会自己递增一位。那么我们只要判断这一位是不是‘’不就可以了吗？所以说，我们的代码还可以写成下面的形式。 char*strstr(constchar*str,char*data) intindex; intlen; if(NULL==str

15、

16、NULL==str) returnNULL; len=strlen(data)