Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1398372
  • 博文数量: 277
  • 博客积分: 2551
  • 博客等级: 少校
  • 技术积分: 3918
  • 用 户 组: 普通用户
  • 注册时间: 2011-02-21 22:46
文章分类

全部博文(277)

文章存档

2017年(3)

2016年(9)

2015年(65)

2014年(27)

2013年(85)

2012年(61)

2011年(27)

分类: 服务器与存储

2012-08-11 23:26:22

  实现一个包含65535个单词的字典,在输入一个字符串后,能找出字符串中在字典中能匹配的所有单词。
  这个一开始,考虑对26个字母进行编码,然后对单词进行数字化,最后只需要对字符串进行拆分,然后得到编码,然后去确定这个编码是否存在,即可得到字符串中的所有在字典中有定义的子串。
   第二种考虑,就是对65535个单词做一个排序,按长度进行分类,初步估计,单词的长度最多为2~30,然后将单词按首字母进行二次分类,每一个长度都有26个不同的首字母,进行2次划分后,仍然存在少量单词。大概计算一下,65535/26=253, 可见每个长度下有253个单词,253/26=10,可见同一长度下每个首次字母开头的单词是10个。
如果这个单词我们采用map实现,而map内部是采用RB-Tree实现,二叉树中的元素的个数与树的深度关系是2^n-1,因为元素是10个,所以树的深度应该是4,不算太深,满足要求。  
   如果,字典中单词的个数达到10w级,这个设计考虑不能满足要求。这时也许要采用第一种方式解决。
阅读(581) | 评论(0) | 转发(0) |
0

上一篇:数据库选型考虑

下一篇:c++中的一些疑点

给主人留下些什么吧!~~