o(1)字符串匹配实现 问题

int ELFhash(char *key)
{ 
    unsigned long h=0;
    while(*key)
    { 
        h=(h<<4)+*key++;
        unsigned long g=h&0Xf0000000L;
        if(g) h^=g>>24;
        h&=~g;
    }
    return h%MOD;
}

1、用ELFhash算法在一篇文章 比如  Good morning. This week, millions of Americans gather with loved ones for Christmas.中查找一个单词millions,那么把每个单词散列到hash表中，查找某单词时候只要将算出该单词hash值，即可判断文章中是否存该单词。如果要得到单词位置，可以弄个结构体，每个单词和起始位置一起存储即可。这样实现应该是算o(1)的吧。

2、然当查询的是mill，即要搜索任意字符串部分，而非单词匹配的时候
比如搜索mill,就要一遍循环计算母串4位hash值，然后进行是否匹配判断，这样就是0(n)的时间度了

问题：如何能实现2情况下o(1)时间阶

10 个解决方案

#1

你的 1  和2  不一样吧
1是在建好hash 之后，但是2 有一个计算hash 的过程

#2

2需要重新计算hash值吧，每四位计算一个存到哈希表中。
这样耗空间,给你推荐用sunday算法吧，百度搜一下就知道是什么了。

#3

引用 1 楼 macrojj 的回复:

你的 1  和2  不一样吧
1是在建好hash 之后，但是2 有一个计算hash 的过程

对的，2是有个计算过程的

#4

O(1)指的是时间不会随着字符串数量增加而增加
因为字符串长度被认为是某个定值，常数系数是可以忽略的

#5

引用 4 楼 do_fork 的回复:

O(1)指的是时间不会随着字符串数量增加而增加
因为字符串长度被认为是某个定值，常数系数是可以忽略的

恩，但是2情况下的o(1)不知道怎么弄？

#6

引用 5 楼 s446721902 的回复:

引用 4 楼 do_fork 的回复:
 O(1)指的是时间不会随着字符串数量增加而增加
 因为字符串长度被认为是某个定值，常数系数是可以忽略的

 恩，但是2情况下的o(1)不知道怎么弄？

如果字符串长度算n，这不可能实现，
因为字符串的每个字符至少要读一遍，所以绝对不可能低于O(n)

#7

引用 6 楼 do_fork 的回复:

引用 5 楼 s446721902 的回复:
引用 4 楼 do_fork 的回复:
O(1)指的是时间不会随着字符串数量增加而增加
因为字符串长度被认为是某个定值，常数系数是可以忽略的

恩，但是2情况下的o(1)不知道怎么弄？


如果字符串长度算n，这不可能实现，
因为字符串的每个字符至少要读一遍，所以绝对不可能低于O(n)

母串的hash过程如果不计，只算匹配过程，那么1情况下应该算是o(1)的吧

#8

匹配任意子串的话，就不能用hash了。可以对母串集先做suffix tree，然后对输入串进行匹配

#9

引用 8 楼 mysword 的回复:

匹配任意子串的话，就不能用hash了。可以对母串集先做suffix tree，然后对输入串进行匹配

thank you ，我试下

#10

引用 8 楼 mysword 的回复:

匹配任意子串的话，就不能用hash了。可以对母串集先做suffix tree，然后对输入串进行匹配

匹配任意字串，我用rolling hash 实现，应该算是o(n)时间阶的。