论坛 › 嵌入式开发 › 寻找字符串

mt_glass 发表于 2018-04-20 09:21

寻找字符串

大家好，向大牛们咨询一个编程问题，
比如有100w个字符串，随机输入一个字符串，判断是不是这个100w个字符串中的？
我的思路是这样的，通过头尾来寻找字符串。
char*p;
char a=xxx
for（i = 0; i < (100w/2); i++）
{
    if(strcmp(p,a) == 0)
    {   
            do_something;
            break;
   }
    if(strcmp(p, a) == 0)
    {   
         do_something;
         break;
   }
}
但是这样100w个字符串也要循环50w次，效率不是很高，有没有更好的方法？
谢谢！

eveson 发表于 2018-05-03 20:23

做出每个字符串的hash去比较

strong46066999 发表于 2018-07-17 15:35

建立N个hash桶，将100w个字符串计算hash值 取模N分布到N个桶中。
输入字符串hash值 取模N 得到桶位置，在桶中比较，

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

spender 发表于 2019-07-22 09:47

去看看 grep 这个源码， 或者学习下 ”字符串搜索“ 算法。

查看完整版本: 寻找字符串