|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
自己写的字符串匹配算法比较,包括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[0] = -1;
- next[1] = 0;
- while (j < size)
- {
- if (i == -1 )
- {
- i++;
- j++;
- next[j] = i;
- }
- if (str[i] == str[j])
- {
- i++;
- j++;
- next[j] = i;
- }
- else
- {
- i = next[i];
- }
- }
- }
复制代码- 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[i] == _str[j])
- {
- i++;
- j++;
- }
- else
- {
- j = next[j];
- }
- 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[i] == _str[j])
- {
- i--;
- j--;
- }
- else
- {
- //咦?匹配错误?那我就在模式串中找到跟这个字符,然后对齐
- while (1)
- {
- j--;
- //找不到,555,怎么办?那就一一个_size的长度咯。
- if (-1 == j)
- {
- i += _size;
- j = _size - 1;
- break;
- }
- //找到了!那就赶紧对齐吧
- if (_str[j] == str[i])
- {
- 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[i] == _str[j])
- {
- 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[pose] == _str[j])
- {
- 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[i]);
- sum += (long)(str[i]);
- }
- i = 0;
- while (j < size)
- {
- if (sum == _sum)
- {
- for (k = 0; k < _size; k++)
- if (str[i + k] != _str[k])
- break;
- if (_size == k)
- return i;
- }
- //删除头元素增加尾元素
- sum = sum - (long)(str[i++]);
- sum = sum + (long)(str[j++]);
- }
- 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[i] == _str[0])
- {
- for (k = 1; k < _size; k++)
- {
- if (str[i + k] != _str[k])
- 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[i] = (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[0xFFFFFF0] = 'i';
- str[0xFFFFFF1] = 'l';
- str[0xFFFFFF2] = 'o';
- str[0xFFFFFF3] = 'v';
- str[0xFFFFFF4] = 'e';
- str[0xFFFFFF5] = 'f';
- str[0xFFFFFF6] = 'i';
- str[0xFFFFFF7] = 's';
- str[0xFFFFFF8] = 'h';
- str[0xFFFFFF9] = '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盘自己看,
怎么能提高呢?
|
|