Sunday Search算法(D.M. Sunday: A Very Fast Substring Search Algorithm. Communications of the ACM, 33, 8, 132-142 (1990))
是大多数情况下比KMP和BM算法更快的串搜索算法,而且原理非常简单易理解.
例如要在”searcqpozreusevnsearch”中搜索”search”
首先初始化一个256长度的索引表,记录每个字节对应搜索串中的倒数位置,即’h’=1,’c’=2,’r’=3,’a’=4,’e’=5,’s’=6,其它字节对应-1
searcqpozreusevnsearch search
第一次循环发现’q’与’h’不等,这时候查看搜索字符串长度后一位’p’在索引表中的值,发现是-1,则直接右移搜索字符串长度+1
searcqpozreusevnsearch -------search
第二次循环,’s’与’o’不同,再查看搜索字符串长度后一位’e’在索引表中值为5,直接右移5位
searcqpozreusevnsearch ------------search
第三次循环,’v’与’a’不同,查询索引表中’a’的值为4,右移4位
searcqpozreusevnsearch ----------------search
第四次循环找到匹配.正常情况下比BM和Horspool都要快很多.
以前拿汇编语言写过,由于最近又需要用到,所以又重新拿C语言写了个,这次把它发到博客上方便以后使用.
#include <string.h> /** * Sunday Search算法C实现 * @author Hoverlees http://www.hoverlees.com */ unsigned char* sunday_search(unsigned char* str,int str_len,unsigned char* sub,int sub_len);
#include "sunday_search.h" unsigned char* sunday_search(unsigned char* str,int str_len,unsigned char* sub,int sub_len){ int marks[256]; int i,j,k; unsigned char *ret=NULL; for(i=0;i<256;i++){ marks[i]=-1; } if(str_len==-1) str_len=strlen(str); if(sub_len==-1) sub_len=strlen(sub); j=0; for(i=sub_len-1;i>=0;i--){ if(marks[sub[i]]==-1){ marks[sub[i]]=sub_len-i; if(++j==256) break; } } i=0; j=str_len-sub_len+1; while(i<j){ for(k=0;k<sub_len;k++){ if(str[i+k]!=sub[k]) break; } if(k==sub_len){ ret=str+i; break; } k=marks[str[i+sub_len]]; if(k==-1) i=i+sub_len+1; else i=i+k; } return ret; }
#include <stdio.h> #include <stdlib.h> #include "sunday_search.h" void main(int argc,char* argv[]){ int i; //字符串测试 char* src="hoverlee hehe xixi asdfasdfadfasdfashoverleesdi1294871-2alsdkjfzafsd hoverlees"; char* sub="hoverlees"; char* r=sunday_search(src,-1,sub,-1); if(r) printf("%s\n",r); else printf("not found\n"); //内存块测试 src=(char*) malloc(8196000); srand(1234567); for(i=0;i<8196000;i++){ src[i]=rand()%256; } sub=(char*) malloc(1024000); for(i=0;i<1024000;i++){ sub[i]=src[1234567+i]; } r=sunday_search(src,8196000,sub,1024000); if(r) printf("%d\n",r-src); else printf("not found\n"); free(src); free(sub); }
sunday search 适合搜索串与被搜索串都是比较长的情况(比如找一个大文件中是否包含某一大段文字), 如果在一个短字符串中找一个短字符串,那就还不如strstr. 因为要初始化一些状态表. 您可以参考我的例子代码里从8196000的内存段中查找1024000长度的内存,可以去尝试一下在一个8196000长的字符串中搜索一个1024000长度的字符串的搜索效率,与strstr的差距
LZ不考虑优化一下?测试1024*1024次比strstr至少慢了5倍
不会,因为str是一个unsigned char数组,里面的任何一个元素值是0-255之间,而marks是个256长度的数组.
sunday_search这个函数里面的29行会出现数组越界吧
你好,不对的地方可以指出来,我也好修改。
不对吧
例子看一遍就理解了,谢谢!