字符串匹配哪家强？（70%几率回帖奖鱼币哦！！）我猜中了开头却没猜中结果。
自己写的字符串匹配算法比较，包括KMP,Horspool，Sunday，BF。不要问我为什么没有BM算法，我他丫的还没搞懂BM的:shutup: 。另外鄙人是一只小菜鸟，写的代码不是很好。
好了，进入正题。。。。。。。。
我第一个写的是KMP算法（基本是抄小甲鱼的代码的:dizzy: ，学了好久了，有个地方还是不太理解。）
void get_next(char *str,long *next,long size)//这个参数应该都懂的。
{
//为什么我要定义为long数据类型呢？看完后面整体代码就知道了
long i = 0,j = 1;
next = -1;
next = 0;
while (j < size)
{
if (i == -1 )
{
i++;
j++;
next = i;
}
if (str == str)
{
i++;
j++;
next = i;
}
else
{
i = next;
}
}
}
long KMP(char *str,char *_str,long size,long _size)//str为匹配串，_str为模式串，size为字串长度
{
long *next = (long *)malloc(sizeof(int)*_size);//为next数组申请空间。
long i = 0, j = 0;
get_next(_str, next, _size);//获得next数组
while (i < size)
{
if (-1 == j )
{
i++;
j++;
}
if (str == _str)
{
i++;
j++;
}
else
{
j = next;
}
if (_size == j)
{
return i - j;
}
}
return -1;
}
KMP算法虽然很难理解，但是感觉代码却很精简啊，其实只要把next数组代码记下来就好了。
KMP算法效率如何呢？下面会有比较的（比较结果也是让我虎躯一震啊）。
接下来是Horspool算法，go，go，go！
Horspool，Sunday，RK都是参考这个的：http://blog.csdn.net/WINCOL/article/details/4795369
long Horspool(char *str, char *_str, long size, long _size)//参数同上面一样，以下也都是一样的
{
//从右到左匹配，别理解错咯，不是从文本的右往左，而是模式串和匹配串对齐后从右往左匹配
long i = _size-1;//i游走在匹配串上
long j = i;//j游走在模式串
while (i < size)
{
//匹配正确，当然要继续往下啦
if (str == _str)
{
i--;
j--;
}
else
{
//咦？匹配错误？那我就在模式串中找到跟这个字符，然后对齐
while (1)
{
j--;
//找不到，555，怎么办？那就一一个_size的长度咯。
if (-1 == j)
{
i += _size;
j = _size - 1;
break;
}
//找到了！那就赶紧对齐吧
if (_str == str)
{
i += _size - j -1;
j = _size - 1;
break;
}
}
}
//j小于0？那不就匹配完了吗！返回结果，欧耶！
if (j < 0)
{
return (i + 1);
}
}
//找不到耶，就返回一个-1吧！
return -1;
}
Horspool算法想法极其简单，但编写代码的时候却耗了我半管血啊！效率如何？不急，慢慢来。
下面是传说中的Sunday算法，据说效率比KMP,BM都要牛逼的多（理想是丰满的，现实总是很骨感的！）。
long Sunday(char *str, char *_str, long size, long _size)
{
//i,j不用讲了，鄙人的习惯。
long i = _size - 1;
long j = _size - 1;
long pose = i + 1;//pose是什么?它是用来指向隔壁老王的，就是匹配串中与模式串对齐的最右端的那个字符的邻居
//哇塞，一进来就直奔主题，直捣龙穴，开门见山般的进入循环，额为什么又是while循环？
//在前面楼主已经说过了，楼主是菜鸟，用for循环比较麻烦，还是while比较简单，我扣扣昵称都叫while(1);呢
while (i < size)
{
//还是Horspool那一套，从前往后匹配
if (str == _str)
{
i--, j--;
}
else
{
//咦，不匹配？那我们就来看看老王在模式串中的位置吧
j = _size - 1;
if (pose >= size)
break;
while (1)
{
//老王不在这里面啊，那没办法了，右移_size个长度去找他吧
if (j < 0)
{
i = pose + _size - 1;
pose = i + 1;
j = _size;
break;
}
//发现野生老王一只，赶紧对齐
if (str == _str)
{
i = pose + _size - j - 1;
pose = i + 1;
j = _size - 1;
break;
}
j--;
}
}
//哟西，轻松找到啦
if (j < 0)
{
return i + 1;
}
}
return -1;
}
我怎么都觉得我的Sunday算法是错误的，求大神指点一二！
没找到C语言版本的Sunday算法代码（找到了，看不懂:cry ），没办法，现在我们也就姑姐认为这就是Sunday算法吧！
完成一大半咯，看看接下来的RK算法，是一种全新的算法哦，我觉得还是很不错的，代码也十分精简，思路也非常简单。
介绍一下RK算法，就是求出模式串的ASCII码值相加总和。然后.....然后在根据限定长度慢慢求出匹配串中字串的总和。
万一子串总和不等于模式串总和怎么办？那就减去子串的头元素再加上尾元素后面一个元素嘛。很好，总和相等耶，那就匹配匹配看看吧。
long RK(char *str, char *_str, long size, long _size)
{
long _sum = 0;
long sum = 0;
long i, j = _size,k = 0;
for (i = 0; i < _size; i++)
{
_sum += (long)(_str);
sum += (long)(str);
}
i = 0;
while (j < size)
{
if (sum == _sum)
{
for (k = 0; k < _size; k++)
if (str != _str)
break;
if (_size == k)
return i;
}
//删除头元素增加尾元素
sum = sum - (long)(str);
sum = sum + (long)(str);
}
return -1;
}
代码异常的简洁。效率嘛，嘿嘿，还是不提。
哇偶！！！！终于到我们最熟悉的BF算法了！！！！！，激动激动！！！！
long BF(char *str, char *_str, long size, long _size)
{
int i = 0, j = 0,k;
while ((i + _size) < size)
{
//楼主想到的新写法，不让i回溯了，太麻烦了。直接一个for循环判断去
if (str == _str)
{
for (k = 1; k < _size; k++)
{
if (str != _str)
break;
}
if (_size == k)
return i;
}
i++;
}
return -1;
}
这才是最简洁的代码嘛！！！！！！！！
好了各个代码展示完毕，感谢各位大神赏脸观赏。接下来揭开字符匹配算法冠军的时候了
:funk: :funk: :funk: :funk: :funk: :funk: :funk: :funk: :funk:
什么！！！！！！！！！！！！！
冠军竟然是BF算法！！！！！！！！！！！！
难道是我写的不对？！！！！！！！！！！！！！！
为什么KMP是最菜的！！！！！！！！！！！？？？？？？？？？？
我感觉我的一生都被骗了！！！！！！！！！！！！！！！！！！！！55555555555555555555
/* 把上述的代码复制粘贴到这里面来就可以正常执行了 */
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<time.h>
#include<windows.h>
//字符串长度
#define MAX_SIZE 0xFFFFFFF
bool get_str(char **str,long size)
{
*str = (char *)malloc
(sizeof(char) * size);
if (NULL == *str)
{
return false;
}
return true;
}
void init_str(char *str)
{
long i;
srand((unsigned)time(NULL));
for (i = 0;i < MAX_SIZE;i++)
{
str = (char)('a' + rand() % 26);
}
}
int main()
{
char *str = NULL;
printf("正在初始化字符串...\n");
get_str(&str, MAX_SIZE);//获得内存
init_str(str);//随机化字符串
//print_str(str,MAX_SIZE);
//固定匹配中字串的位置
str = 'i';
str = 'l';
str = 'o';
str = 'v';
str = 'e';
str = 'f';
str = 'i';
str = 's';
str = 'h';
str = 'c';
LARGE_INTEGER start;
LARGE_INTEGER end;
LARGE_INTEGER freq;
/*************************************/
/** KMP **/
/*************************************/
/**/printf("KMP算法匹配开始！\n");
/**/QueryPerformanceFrequency(&freq);
/**/QueryPerformanceCounter(&start);
/**/long i = KMP(str, "ilovefishc", MAX_SIZE, 10);
/**/QueryPerformanceCounter(&end);
/**/printf("KMP算法：\n字符串在第 %X个位置处！\n", i);
/**/printf("共用了 : %.10f s\n",
/**/ (double)(end.QuadPart - start.QuadPart) / (double)freq.QuadPart);
/*************************************/
/** Horspool **/
/*************************************/
/**/printf("Horspool算法匹配开始！\n");
/**/QueryPerformanceFrequency(&freq);
/**/QueryPerformanceCounter(&start);
/**/long j = Horspool(str, "ilovefishc", MAX_SIZE, 10);
/**/QueryPerformanceCounter(&end);
/**/printf("Horspool算法：\n字符串在第 %X 个位置处！\n", j);
/**/printf("共用了 : %.10f s\n",
/**/ (double)(end.QuadPart - start.QuadPart) / (double)freq.QuadPart);
/*************************************/
/*************************************/
/** Sunday **/
/*************************************/
/**/printf("Sunday算法匹配开始！\n");
/**/QueryPerformanceFrequency(&freq);
/**/QueryPerformanceCounter(&start);
/**/long s = Sunday(str, "ilovefishc", MAX_SIZE, 10);
/**/QueryPerformanceCounter(&end);
/**/printf("Sunday算法：\n字符串在第 %X 个位置处！\n", s);
/**/printf("共用了 : %.10f s\n",
/**/ (double)(end.QuadPart - start.QuadPart) / (double)freq.QuadPart);
/*************************************/
/*************************************/
/** RK **/
/*************************************/
/**/printf("RK算法匹配开始！\n");
/**/QueryPerformanceFrequency(&freq);
/**/QueryPerformanceCounter(&start);
/**/long r = RK(str, "ilovefishc", MAX_SIZE, 10);
/**/QueryPerformanceCounter(&end);
/**/printf("RK算法：\n字符串在第 %X 个位置处！\n", r);
/**/printf("共用了 : %.10f s\n",
/**/ (double)(end.QuadPart - start.QuadPart) / (double)freq.QuadPart);
/*************************************/
/*************************************/
/** BF **/
/*************************************/
/**/printf("BF算法匹配开始！\n");
/**/QueryPerformanceFrequency(&freq);
/**/QueryPerformanceCounter(&start);
/**/long b = BF(str, "ilovefishc", MAX_SIZE, 10);
/**/QueryPerformanceCounter(&end);
/**/printf("BF算法：\n字符串在第 %X 个位置处！\n", b);
/**/printf("共用了 : %.10f s\n",
/**/ (double)(end.QuadPart - start.QuadPart) / (double)freq.QuadPart);
/*************************************/
return 0;
}
接下来是颁奖仪式：
有请第一名BF上台领奖！！！！！！！掌声在哪里？？？啪啪啪，啪啪啪......（啪！）
有请最后一名KMP上台领奖：挡挡挡，挡挡挡！挡挡，挡挡！……
颁奖结束，求别打脸！！！！！！
谈谈心里话：
逗比的花了两天时间写的，求大神赐教，本屌真心不是向各位还没学的朋友们炫耀，只是想把代码贴出来分享，
我的水平不高，写不出大师级别的代码，只能不断的来锻炼，来完善自己，若代码只保存在自己的 D盘自己看，
怎么能提高呢？
2楼也是我的。
我还得声明一下，其实这个数据并不代表这些算法在实际中的效率，写代码的人的水平对算法的实现的效率也会有一定的影响的。，我想可能是我写的代码太渣了才会出现这种结果吧》！ :big 我发了一贴,用了你的代码来测试 ,发现我的那个个算法好像比上述代码都要快 ,不直到是测试方式不对还是什么其他别的原因 错过会难过 发表于 2015-8-20 19:16
我发了一贴,用了你的代码来测试 ,发现我的那个个算法好像比上述代码都要快 ,不直到是测试方式不对还是什么 ...
可能是小弟水平太菜了，或者电脑配置太菜了。 新人来看看！以便能加深记忆！{:5_91:} 拿奖励去学习 支持楼主！
页:
[1]