Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3583065
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8580
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: C/C++

2011-12-22 18:22:19

    遇到一个题目,两个字符串,一个长字符串,一个子串,在长字符串中删除,任何出现在短字符串的函数。
    开始以为是模式匹配的题目,后来发现不是文章BM算法中搜索子串的功能,当时慌了神。现在想想,其实并不是很难。

如 长字符串:abcdefhijklmnbcd
   子串:     bk
   结果:    acdefhijlmncd
删除长字符串中所有的b和k。

    字符共有有256个(BYTE是8个bit),只需要维护一个长度为256的数组exist,1表示该字符出现在子串中如exist[‘b’] = 1,0表示没有出现在子串中exist['c'] =0,那么.遍历一遍长字符串,就可以删除那些子串的字符。

    如果长字符串的长度为N,字串的长度为M,算法复杂度为(M+N)。比较节省,暴力搜索需要M*N的算法复杂度。
    自己还是不能活学活用,本来这个算法只是BM算法的一部分,竟然没想到。记之。


  1. root@libin:~/program/C/string# ./test
  2. this is a long string ,abcdefg
  3. gi
  4. ths s a lon strn ,abcdef

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>



  4. int delchar(char* src,char* del,char* dest)
  5. {
  6.                 if(src == NULL ||del==NULL||dest == NULL)
  7.                                 return -1;

  8.                 int dellen = strlen(del);
  9.                 int existed[256] ;
  10.                 int i;
  11.                 int srclen = strlen(src);
  12.                 int j = 0;
  13.                 
  14.                 for(i = 0;i<256;i++ )
  15.                 {
  16.                                 existed[i] = 0;
  17.                 }

  18.                 for(i = 0;i<dellen;i++ )
  19.                 {
  20.                                 existed[del[i]] = 1;
  21.                 }

  22.                 for(i = 0;i<srclen;i++ )
  23.                 {
  24.                                 if(existed[src[i]])
  25.                                                 continue;
  26.                                 dest[j++] = src[i];
  27.                 }
  28.                 return 0;
  29. }

  30. int test()
  31. {
  32.                 char longstr[] = "this is a long string ,abcdefg";
  33.                 char shortstr[]= "gi";

  34.                 int len = strlen(longstr);
  35.                 char *resultstr = (char*)malloc(len);
  36.                 if(resultstr == NULL)
  37.                 {
  38.                                 fprintf(stderr,"malloc for result str failed\n");
  39.                                 return -1;
  40.                 }
  41.                 delchar(longstr,shortstr,resultstr);
  42.                 printf("%s\n%s\n%s\n",longstr,shortstr,resultstr);

  43.                 free(resultstr);
  44.                 return 0;
  45. }
  46. int main()
  47. {
  48.                 test();
  49.                 return 0;
  50. }
阅读(4771) | 评论(2) | 转发(0) |
给主人留下些什么吧!~~

Bean_lee2011-12-27 23:05:13

前辈说的对。今天下班有点晚,呵呵,所以回复的晚了点。暂时不修改,抽时间该一下。

Heartwork2011-12-27 10:26:45

delchar函数最后需要将dest末尾加\0。