字符串查找算法中,最著名的两个是KMP算法(Knuth-Morris-Pratt)和BM算法(Boyer-Moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上,KMP算法并不比最简单的c库函数strstr()快多少,而BM算法则往往比KMP算法快上3-5倍。
但是,最坏的情况下,BM的时间复杂度貌似也是n×n。
具体就不说了,BM算法是通过往后跳动主文本字符串来实现快速非回溯查找的,跳动的算法就是用程序中的这句来实现的,下面:
- i=i+m-min(j,1+last(p,T[i]));
而last是一个求文本字符串中的字符在查找字符串里面出现的最后位置。
这个算法很麻烦,呵呵,可以的话百度一下。
整个代码如下:
- #include<string.h>
-
intlast(char*p,charc){
-
intlength=strlen(p),count=0;
-
char*pp=p+length-1;
-
while(pp>=p)
- {
-
if(*pp==c)
- {
-
returnlength-count-1;
- }
- pp--;
- count++;
- }
-
return-1;
- }
-
-
intmin(inta,intb){
-
return(a<=b)?a:b;
- }
-
-
intBM_index(char*T,char*p){
-
intn=strlen(T);
-
intm=strlen(p);
-
inti=m-1,j=m-1;
-
while(i<=n-1)
- {
-
if(T[i]==p[j])
- {
-
if(j==0)
- {
-
returni;
- }
-
else
- i--,j--;
- }
-
else{
-
i=i+m-min(j,1+last(p,T[i]));
- j=m-1;
- }
- }
-
return-1;
- }
-
-
int_tmain(intargc,_TCHAR*argv[])
- {
-
char*p="woainizz!izzzzzz--zzzzut";
-
inta=BM_index(p,"zzzzut");
-
return0;
- }
分享到:
相关推荐
字符串查找源码,
C strstr字符串查找函数优化,解决查找中文汉字匹配存在错误BUG问题。支持GBK、GB18030字符串。
字符串查找替换 程序设计 课程设计 报告
多文件中字符串查找工具 多文件中字符串查找工具
字符串查找KMP算法
一款字符串查找、替换的好工具,非常好用。
字符串查找工具字符串查找工具
给出了数据结构中字符串查找的方法解决您的难题
该程序是我写的博客“一起talk C栗子吧(第六十三回:C语言实例--字符串查找)”的配套程序,共享给大家使用
VB之字符串精彩编程-字符串查找和替换的实现例子(1KB)
字符串查找替换,多文件字符串查找替换,批量查找多文件的某一个字符,批量替换某一个字符等。
字符串查找和替换的实现例子(1KB)
此工具可以用来查找文件夹里的所有文件中的字符串,十分方便
但在实际的工作中,还是会遇到一些特殊情况的处理,这使得直接使用字符串查找函数,得到的结果可能是错误的,比如本文中提到的固定长度编码格式的字符串的查找。本文介绍了通用固定长度编码格式的字符串查找算法的...
一本全面彻底讲解字符串查找算法的书。 书中讲解了34个字符串查找算法的思想。每个算法都有适用性的描述。每个算法都有逐步推演的例子(图解)。每个算法都有代码(C语言)。每个算法都有复杂度分析。每个算法都有...
字符串查找替换
文件 字符串 查找 替换 批量 小巧 文件 字符串 查找 替换 批量 小巧
字符串查找替换工具2.2
字符串查找替换 小巧实用,方便,快速