免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 10285 | 回复: 3

[应用] 寻找字符串 [复制链接]

论坛徽章:
1
2015亚冠之塔什干火车头
日期:2015-06-08 10:15:34
发表于 2018-04-20 09:21 |显示全部楼层
大家好,向大牛们咨询一个编程问题,
比如有100w个字符串,随机输入一个字符串,判断是不是这个100w个字符串中的?
我的思路是这样的,通过头尾来寻找字符串。
char*p[100w];
char a=xxx
for(i = 0; i < (100w/2); i++)
{
    if(strcmp(p[i],a) == 0)
    {   
            do_something;
            break;
     }
    if(strcmp(p[100w-1-i], a) == 0)
    {   
           do_something;
           break;
     }
}
但是这样100w个字符串也要循环50w次,效率不是很高,有没有更好的方法?
谢谢!


论坛徽章:
0
发表于 2018-05-03 20:23 来自手机 |显示全部楼层
做出每个字符串的hash去比较

论坛徽章:
1
2015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2018-07-17 15:35 |显示全部楼层
建立N个hash桶,将100w个字符串计算hash值 取模N分布到N个桶中。
输入字符串hash值 取模N 得到桶位置,在桶中比较,

1. 如果桶中的可以有序可以二分快些。
2. 不考虑内存把桶数据放大些。

论坛徽章:
1
IT运维版块每日发帖之星
日期:2016-03-04 06:20:00
发表于 2019-07-22 09:47 |显示全部楼层
去看看 grep 这个源码, 或者学习下 ”字符串搜索“ 算法。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。




----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP