寻找字符串

mt_glass

大家好，向大牛们咨询一个编程问题，
比如有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次，效率不是很高，有没有更好的方法？
谢谢！

eveson

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

strong46066999

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

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

spender

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