关于串匹配问题之莫名的超超高效率匹配
这是我的strstr实现:
char *qsearch(const char *str, int slen, const char *patt, int plen)
{
const char *s, *p, *tx = str;
static int td[128],c=0;
/*************预处理*****************************/
for ( ++plen; c < 128; ++c) //建立表
td[c] = plen ;
--plen; //复原
for (p=patt; *p; p++) //初始化表
td[*p] = plen - (p - patt);//m-(p-patt)即失配时模式串右移的步数
/***************模式匹配开始*********************/
while ( (s=tx+plen-1) <= str+slen-1) {
for (p = patt+plen-1; *p == *s; --s)
--p;
if (*p == 0) // 找到并返回
return (char*)tx;
tx += td[tx[plen]]; // 模式右移
}
return NULL;
}
一:这个是网上找到strstr实现1
char * strstr (buf, sub)
register char *buf;
register char *sub;
{
register char *bp;
register char *sp;
if (!*sub)
return buf;
while (*buf)
{
bp = buf;
sp = sub;
do {
if (!*sp)
return buf;
} while (*bp++ == *sp++);
buf += 1;
}
return 0;
}
二:这是gcc的实现
const char * bstrstr(const char *src, const char *needle)
{
const char *p1, *p2;
p1 = src;
p2 = needle;
while (*src != '\0' && *needle != '\0')
{
if (*src++ != *needle++) {
needle = p2;
src = ++p1; //从下一个字符开始搜索needle
}
}
if (*needle == '\0')
return p1;
return NULL;
}
测试字符串char *s="sjuwfdjkasbUYTGdflksjflkhjdslkdlkfhjBWEVFBSDJKJBHSDsaFdfasIUasGW
EFkasfhskaddsajiudvdbkajdsfgviausdgEJSAHDKJAKJGHhsadhbjjh";
char *t="sad";
进行一千万次
有个很奇怪的现象,我的实现(sunday) 的时间是 3062ms,kmp算法实现是 9112ms,一的实现是1133ms
可是gcc那个实现竟然是36ms!!!
gcc那个实现和一的实现可以说没区别,都是朴素匹配,为什么那个时间那么快!!!?????????