鱼C论坛

 找回密码
 立即注册
查看: 4106|回复: 7

[技术交流] 字符串匹配哪家强?(70%几率回帖奖鱼币哦!!)我猜中了开头却没猜中结果。

[复制链接]
发表于 2015-7-29 19:44:12 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
自己写的字符串匹配算法比较,包括KMP,Horspool,Sunday,BF。不要问我为什么没有BM算法,我他丫的还没搞懂BM的:shutup: 。

另外鄙人是一只小菜鸟,写的代码不是很好。

好了,进入正题。。。。。。。。


我第一个写的是KMP算法(基本是抄小甲鱼的代码的:dizzy: ,学了好久了,有个地方还是不太理解。)
  1. void get_next(char *str,long *next,long size)//这个参数应该都懂的。
  2. {
  3.         //为什么我要定义为long数据类型呢?看完后面整体代码就知道了
  4.         long i = 0,j = 1;
  5.         next[0] = -1;
  6.         next[1] = 0;
  7.         while (j < size)
  8.         {
  9.                 if (i == -1 )
  10.                 {
  11.                         i++;
  12.                         j++;
  13.                         next[j] = i;
  14.                 }
  15.                 if (str[i] == str[j])
  16.                 {
  17.                         i++;
  18.                         j++;
  19.                         next[j] = i;
  20.                 }
  21.                 else
  22.                 {
  23.                         i = next[i];
  24.                 }
  25.         }
  26. }
复制代码
  1. long KMP(char *str,char *_str,long size,long _size)//str为匹配串,_str为模式串,size为字串长度
  2. {
  3.         long *next = (long *)malloc(sizeof(int)*_size);//为next数组申请空间。
  4.         long i = 0, j = 0;
  5.         get_next(_str, next, _size);//获得next数组
  6.         while (i < size)
  7.         {
  8.                 if (-1 == j )
  9.                 {
  10.                         i++;
  11.                         j++;
  12.                 }
  13.                 if (str[i] == _str[j])
  14.                 {
  15.                         i++;
  16.                         j++;
  17.                 }
  18.                 else
  19.                 {
  20.                         j = next[j];
  21.                 }
  22.                 if (_size == j)
  23.                 {
  24.                         return i - j;
  25.                 }
  26.         }
  27.         return -1;
  28. }
复制代码


KMP算法虽然很难理解,但是感觉代码却很精简啊,其实只要把next数组代码记下来就好了。
KMP算法效率如何呢?下面会有比较的(比较结果也是让我虎躯一震啊)。

接下来是Horspool算法,go,go,go!
Horspool,Sunday,RK都是参考这个的:http://blog.csdn.net/WINCOL/article/details/4795369


  1. long Horspool(char *str, char *_str, long size, long _size)//参数同上面一样,以下也都是一样的
  2. {
  3.         //从右到左匹配,别理解错咯,不是从文本的右往左,而是模式串和匹配串对齐后从右往左匹配
  4.         long i = _size-1;//i游走在匹配串上
  5.         long j = i;//j游走在模式串
  6.         while (i < size)
  7.         {
  8.                 //匹配正确,当然要继续往下啦
  9.                 if (str[i] == _str[j])
  10.                 {
  11.                         i--;
  12.                         j--;
  13.                 }
  14.                 else
  15.                 {
  16.                         //咦?匹配错误?那我就在模式串中找到跟这个字符,然后对齐
  17.                         while (1)
  18.                         {
  19.                                 j--;
  20.                                 //找不到,555,怎么办?那就一一个_size的长度咯。
  21.                                 if (-1 == j)
  22.                                 {
  23.                                         i += _size;
  24.                                         j = _size - 1;
  25.                                         break;
  26.                                 }
  27.                                 //找到了!那就赶紧对齐吧
  28.                                 if (_str[j] == str[i])
  29.                                 {
  30.                                         i += _size - j -1;
  31.                                         j = _size - 1;
  32.                                         break;
  33.                                 }
  34.                         }
  35.                 }
  36.                 //j小于0?那不就匹配完了吗!返回结果,欧耶!
  37.                 if (j < 0)
  38.                 {
  39.                         return (i + 1);
  40.                 }
  41.         }
  42.         //找不到耶,就返回一个-1吧!
  43.         return -1;
  44. }
复制代码

Horspool算法想法极其简单,但编写代码的时候却耗了我半管血啊!效率如何?不急,慢慢来。


下面是传说中的Sunday算法,据说效率比KMP,BM都要牛逼的多(理想是丰满的,现实总是很骨感的!)。

  1. long Sunday(char *str, char *_str, long size, long _size)
  2. {
  3.         //i,j不用讲了,鄙人的习惯。
  4.         long i = _size - 1;
  5.         long j = _size - 1;
  6.         long pose = i + 1;//pose是什么?它是用来指向隔壁老王的,就是匹配串中与模式串对齐的最右端的那个字符的邻居
  7.         //哇塞,一进来就直奔主题,直捣龙穴,开门见山般的进入循环,额为什么又是while循环?
  8.         //在前面楼主已经说过了,楼主是菜鸟,用for循环比较麻烦,还是while比较简单,我扣扣昵称都叫while(1);呢
  9.         while (i < size)
  10.         {
  11.                 //还是Horspool那一套,从前往后匹配
  12.                 if (str[i] == _str[j])
  13.                 {
  14.                         i--, j--;
  15.                 }
  16.                 else
  17.                 {
  18.                 //咦,不匹配?那我们就来看看老王在模式串中的位置吧
  19.                         j = _size - 1;
  20.                         if (pose >= size)
  21.                                 break;
  22.                         while (1)
  23.                         {
  24.                                 //老王不在这里面啊,那没办法了,右移_size个长度去找他吧
  25.                                 if (j < 0)
  26.                                 {
  27.                                         i = pose + _size - 1;
  28.                                         pose = i + 1;
  29.                                         j = _size;
  30.                                         break;
  31.                                 }
  32.                                 //发现野生老王一只,赶紧对齐
  33.                                 if (str[pose] == _str[j])
  34.                                 {
  35.                                         i = pose + _size - j - 1;
  36.                                         pose = i + 1;
  37.                                         j = _size - 1;
  38.                                         break;
  39.                                 }
  40.                                 j--;
  41.                         }
  42.                 }
  43.                 //哟西,轻松找到啦
  44.                 if (j < 0)
  45.                 {
  46.                         return i + 1;
  47.                 }
  48.         }
  49.         return -1;
  50.        
  51. }
复制代码

我怎么都觉得我的Sunday算法是错误的,求大神指点一二!
没找到C语言版本的Sunday算法代码(找到了,看不懂:cry ),没办法,现在我们也就姑姐认为这就是Sunday算法吧!


完成一大半咯,看看接下来的RK算法,是一种全新的算法哦,我觉得还是很不错的,代码也十分精简,思路也非常简单。
介绍一下RK算法,就是求出模式串的ASCII码值相加总和。然后.....然后在根据限定长度慢慢求出匹配串中字串的总和。
万一子串总和不等于模式串总和怎么办?那就减去子串的头元素再加上尾元素后面一个元素嘛。很好,总和相等耶,那就匹配匹配看看吧。

  1. long RK(char *str, char *_str, long size, long _size)
  2. {
  3.         long _sum = 0;
  4.         long sum = 0;
  5.         long i, j = _size,k = 0;
  6.         for (i = 0; i < _size; i++)
  7.         {
  8.                 _sum += (long)(_str[i]);
  9.                 sum += (long)(str[i]);
  10.         }
  11.         i = 0;
  12.         while (j < size)
  13.         {
  14.                 if (sum == _sum)
  15.                 {
  16.                         for (k = 0; k < _size; k++)
  17.                                 if (str[i + k] != _str[k])
  18.                                         break;
  19.                         if (_size == k)
  20.                                 return i;
  21.                 }
  22.                 //删除头元素增加尾元素
  23.                 sum = sum - (long)(str[i++]);
  24.                 sum = sum + (long)(str[j++]);
  25.         }
  26.         return -1;
  27. }
复制代码


代码异常的简洁。效率嘛,嘿嘿,还是不提。




哇偶!!!!终于到我们最熟悉的BF算法了!!!!!,激动激动!!!!



  1. long BF(char *str, char *_str, long size, long _size)
  2. {
  3.         int i = 0, j = 0,k;
  4.         while ((i + _size) < size)
  5.         {
  6.                 //楼主想到的新写法,不让i回溯了,太麻烦了。直接一个for循环判断去
  7.                 if (str[i] == _str[0])
  8.                 {
  9.                         for (k = 1; k < _size; k++)
  10.                         {
  11.                                 if (str[i + k] != _str[k])
  12.                                         break;
  13.                         }
  14.                         if (_size == k)
  15.                                 return i;
  16.                 }
  17.                 i++;
  18.         }
  19.         return -1;
  20. }
复制代码

这才是最简洁的代码嘛!!!!!!!!

好了各个代码展示完毕,感谢各位大神赏脸观赏。接下来揭开字符匹配算法冠军的时候了

_WA)LWNA2YJB)3_Z%[P4(5U.jpg

:funk: :funk: :funk: :funk: :funk: :funk: :funk: :funk: :funk:
什么!!!!!!!!!!!!!
冠军竟然是BF算法!!!!!!!!!!!!
难道是我写的不对?!!!!!!!!!!!!!!
为什么KMP是最菜的!!!!!!!!!!!??????????
我感觉我的一生都被骗了!!!!!!!!!!!!!!!!!!!!55555555555555555555


  1. /*         把上述的代码复制粘贴到这里面来就可以正常执行了            */
  2. #include<stdio.h>
  3. #include<malloc.h>
  4. #include<stdlib.h>
  5. #include<time.h>
  6. #include<windows.h>
  7. //字符串长度
  8. #define MAX_SIZE 0xFFFFFFF
  9. bool get_str(char **str,long size)
  10. {
  11.         *str = (char *)malloc
  12.                 (sizeof(char) * size);
  13.         if (NULL == *str)
  14.         {
  15.                 return false;
  16.         }
  17.         return true;
  18. }
  19. void init_str(char *str)
  20. {
  21.         long i;
  22.         srand((unsigned)time(NULL));
  23.         for (i = 0;i < MAX_SIZE;i++)
  24.         {
  25.                 str[i] = (char)('a' + rand() % 26);
  26.         }
  27. }
  28. int main()
  29. {
  30.         char *str = NULL;
  31.         printf("正在初始化字符串...\n");
  32.         get_str(&str, MAX_SIZE);//获得内存
  33.         init_str(str);//随机化字符串
  34.         //print_str(str,MAX_SIZE);
  35.         //固定匹配中字串的位置
  36.         str[0xFFFFFF0] = 'i';
  37.         str[0xFFFFFF1] = 'l';
  38.         str[0xFFFFFF2] = 'o';
  39.         str[0xFFFFFF3] = 'v';
  40.         str[0xFFFFFF4] = 'e';
  41.         str[0xFFFFFF5] = 'f';
  42.         str[0xFFFFFF6] = 'i';
  43.         str[0xFFFFFF7] = 's';
  44.         str[0xFFFFFF8] = 'h';
  45.         str[0xFFFFFF9] = 'c';
  46.         LARGE_INTEGER start;
  47.         LARGE_INTEGER end;
  48.         LARGE_INTEGER freq;
  49.        
  50.         /*************************************/
  51.         /**           KMP                   **/
  52.         /*************************************/
  53.         /**/printf("KMP算法匹配开始!\n");
  54.         /**/QueryPerformanceFrequency(&freq);
  55.         /**/QueryPerformanceCounter(&start);
  56.         /**/long i = KMP(str, "ilovefishc", MAX_SIZE, 10);
  57.         /**/QueryPerformanceCounter(&end);
  58.         /**/printf("KMP算法:\n字符串在第 %X个位置处!\n", i);
  59.         /**/printf("共用了 : %.10f s\n",
  60.         /**/        (double)(end.QuadPart - start.QuadPart) / (double)freq.QuadPart);
  61.         /*************************************/
  62.         /**            Horspool             **/
  63.         /*************************************/
  64.         /**/printf("Horspool算法匹配开始!\n");
  65.         /**/QueryPerformanceFrequency(&freq);
  66.         /**/QueryPerformanceCounter(&start);
  67.         /**/long j = Horspool(str, "ilovefishc", MAX_SIZE, 10);
  68.         /**/QueryPerformanceCounter(&end);
  69.         /**/printf("Horspool算法:\n字符串在第 %X 个位置处!\n", j);
  70.         /**/printf("共用了 : %.10f s\n",
  71.         /**/        (double)(end.QuadPart - start.QuadPart) / (double)freq.QuadPart);
  72.         /*************************************/
  73.         /*************************************/
  74.         /**            Sunday               **/
  75.         /*************************************/
  76.         /**/printf("Sunday算法匹配开始!\n");
  77.         /**/QueryPerformanceFrequency(&freq);
  78.         /**/QueryPerformanceCounter(&start);
  79.         /**/long s = Sunday(str, "ilovefishc", MAX_SIZE, 10);
  80.         /**/QueryPerformanceCounter(&end);
  81.         /**/printf("Sunday算法:\n字符串在第 %X 个位置处!\n", s);
  82.         /**/printf("共用了 : %.10f s\n",
  83.         /**/        (double)(end.QuadPart - start.QuadPart) / (double)freq.QuadPart);
  84.         /*************************************/
  85.         /*************************************/
  86.         /**            RK                   **/
  87.         /*************************************/
  88.         /**/printf("RK算法匹配开始!\n");
  89.         /**/QueryPerformanceFrequency(&freq);
  90.         /**/QueryPerformanceCounter(&start);
  91.         /**/long r = RK(str, "ilovefishc", MAX_SIZE, 10);
  92.         /**/QueryPerformanceCounter(&end);
  93.         /**/printf("RK算法:\n字符串在第 %X 个位置处!\n", r);
  94.         /**/printf("共用了 : %.10f s\n",
  95.         /**/        (double)(end.QuadPart - start.QuadPart) / (double)freq.QuadPart);
  96.         /*************************************/
  97.         /*************************************/
  98.         /**            BF                   **/
  99.         /*************************************/
  100.         /**/printf("BF算法匹配开始!\n");
  101.         /**/QueryPerformanceFrequency(&freq);
  102.         /**/QueryPerformanceCounter(&start);
  103.         /**/long b = BF(str, "ilovefishc", MAX_SIZE, 10);
  104.         /**/QueryPerformanceCounter(&end);
  105.         /**/printf("BF算法:\n字符串在第 %X 个位置处!\n", b);
  106.         /**/printf("共用了 : %.10f s\n",
  107.         /**/        (double)(end.QuadPart - start.QuadPart) / (double)freq.QuadPart);
  108.         /*************************************/
  109.         return 0;
  110. }
复制代码




接下来是颁奖仪式:
有请第一名BF上台领奖!!!!!!!掌声在哪里???啪啪啪,啪啪啪......(啪!)
有请最后一名KMP上台领奖:挡挡挡,挡挡挡!挡挡,挡挡!……
颁奖结束,求别打脸!!!!!!

谈谈心里话:
逗比的花了两天时间写的,求大神赐教,本屌真心不是向各位还没学的朋友们炫耀,只是想把代码贴出来分享,
我的水平不高,写不出大师级别的代码,只能不断的来锻炼,来完善自己,若代码只保存在自己的 D盘自己看,
怎么能提高呢?

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2015-7-29 19:52:00 | 显示全部楼层
2楼也是我的。
我还得声明一下,其实这个数据并不代表这些算法在实际中的效率,写代码的人的水平对算法的实现的效率也会有一定的影响的。,我想可能是我写的代码太渣了才会出现这种结果吧》!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2015-7-29 21:56:40 | 显示全部楼层

回帖奖励 +1 鱼币

:big
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-20 19:16:37 | 显示全部楼层
我发了一贴,用了你的代码来测试 ,发现我的那个个算法好像比上述代码都要快 ,不直到是测试方式不对还是什么其他别的原因
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2015-8-26 20:34:46 | 显示全部楼层
错过会难过 发表于 2015-8-20 19:16
我发了一贴,用了你的代码来测试 ,发现我的那个个算法好像比上述代码都要快 ,不直到是测试方式不对还是什么 ...

可能是小弟水平太菜了,或者电脑配置太菜了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-2-20 11:17:09 | 显示全部楼层
新人来看看!以便能加深记忆!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-9-14 14:22:03 | 显示全部楼层
拿奖励去学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-14 08:49:15 | 显示全部楼层
支持楼主!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 00:30

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表