Processing math: 100%

AcWing 841. 字符串哈希    原题链接    简单

作者： 作者的头像   一只学术蜗牛 ,  2024-03-10 11:42:28 ,  所有人可见 ,  阅读 43

1


点击此处获取更多干货

字符串前缀哈希算法

字符串的哈希算法，此前已经出现了不少知名算法，如谷歌开发出的CityHash和FarmHash，STL中采用的FNV-1a，以及非常简单粗暴的BKDR。本次先介绍BKDR算法，它不仅具有一般字符串哈希算法的特点，还有着像前缀和算法那样快速的取得字符串中任意子串哈希值的特异功能。

BKDR算法简单粗暴的地方在于它把字符串当成了另一种进制之下的整数，用这个“整数”的10进制表示当成了该字符串的哈希值。考虑到这个数可能很大，还需要对其取模。如果确定了算法中使用的基数(base)和模数(mod)，长度为L的字符串str对应的哈希值为：
H(L)=(L−1∑i=0((str[i]∗baseL−1−i)%mod))%mod

由于字符(char)类型和整数类型存储的方式相似，所以字符可以直接转成哈希函数需要的返回值类型size_t。基数base可以取略大于128的奇数，模数mod尽量取大，最好取远大于基数的质数或者直接取size_t类型最大值264−1，如果去掉上述公式中所有的取模运算，那么模数默认就是264−1，这种方式也叫做自动溢出方式

忽略取模操作，将求和式展开，并将str[i]视作size_t类型，关注一下H(L)和H(L−1)的关系：
H(L)=str[0]∗baseL−1+str[1]∗baseL−2+…+str[L−2]∗base1+str[L−1]∗base0
H(L−1)=str[0]∗baseL−2+str[1]∗baseL−3+…+str[L−2]∗base0
可以发现H(L)的展开式中，直到str[L−2]项为止，其中每一项都比H(L−1)对应的项多乘了一次base，那么我们也可以得出字符串前缀的哈希递推公式H(L)=H(L−1)∗base+str[L−1]

对于在[s,e]区间之内的子串，可以将主串首端视作高位，尾端视作低位，像处理一般的10进制数那样，下面举例图解：
0806319d71f3e6605e766c784c588ed.png
[5,8]区间上的子串Rain相当于长度8的前缀“MildRain”中去掉了长度4的前缀“Mild”，相当于在基数为base的进制之下左移了4位后相减，对应到哈希值中就是H(8)−H(4)∗base4，由此可得出区间[s,e]之间的子串的哈希公式为：
prefixHash(s,e)=H(e)−H(s−1)∗basee−s+1
加上了取模就变为：
prefixHash(s,e)=((H(e)−(H(s−1)∗basee−s+1)%mod)+mod)%mod
这里最好先加后取模，因为如果出现了负数，在size_t类型下会自动对264−1取模，内外模数不相同可能会出差错

如果把不同长度的前缀哈希值以及基数的各幂值事先算好并记录下来，那就可以像前缀和那样，套用上面的公式，在常数时间内通过两端点位置得子串哈希值。由于它和前缀和思想有些类似，因此也可以叫做“字符串前缀哈希算法”

C++ 代码

哈希函数的定义方法和STL相同，都是定义成结构体仿函数，模板化并用size_t类型做模板参数，是为了方便选择模数和基数。仅使用一组模数和基数叫做“单模”方法，如果模数取了264−1就是“自动溢出”方法。为了进一步减少冲突还可以选择多组模数和基数（“多模”方法，2∼3组就足够）

//这些要和哈希仿函数prefixHash一同使用
string text;
const size_t modList[] = { ULLONG_MAX, 9999971, 9999973 };
const size_t hashBase[] = { 131, 131, 151 };

//模板参数modIdx用于选择模数和基数
template<size_t modIdx>
struct PrefixHash {
    //事先算好hashBase的幂（取模后的值），以及不同长度的字符串前缀对应的哈希值
    size_t* prefixHashCode, * weight;

    PrefixHash() {
        //多个哈希函数用于同一个字符串时，不用重复输入
        if (text.empty()) {
            cin >> text;
        }
        prefixHashCode = new size_t[text.size() + 1]();//C++20之前可以在new[]后加空括号默认赋值
        weight = new size_t[text.size() + 1];
        weight[0] = 1;
        //按位执行哈希计算，并事先保存
        for (int i = 1; i <= text.size(); i++) {
            weight[i] = (weight[i - 1] * hashBase[modIdx]) % modList[modIdx];
            prefixHashCode[i] =
                (prefixHashCode[i - 1] * hashBase[modIdx] + (size_t)text[i - 1]) % modList[modIdx];
        }
    }

    //重载()取得[begin,end]之间子串的哈希值
    size_t operator()(int begin, int end) {
        return (prefixHashCode[end] 
            - prefixHashCode[begin - 1] * weight[end - begin + 1] % modList[modIdx]
            + modList[modIdx]) % modList[modIdx];//最好是先加后取模
    }

    ~PrefixHash() {
        delete[] weight, prefixHashCode;
    }
};

同一个字符串两个不同区间上的子串是否相同，就看它们对应的哈希值是否相同，包含该判断过程的程序主函数如下：

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    //只构造一个哈希仿函数就是单模方法，构造多个一起用就是多模，单模时模板参数0对应的就是自动溢出
    PrefixHash<0> hasher;
    int l1, l2, r1, r2;
    while (m--) {
        cin >> l1 >> l2 >> r1 >> r2;
        //取得两个区间上子串的哈希值，判断是否相同
        size_t hashCodeL = hasher(l1, l2), hashCodeR = hasher(r1, r2);
        cout << ((hashCodeL == hashCodeR) ? "Yes" : "No") << endl;
    }
    return 0;
}

0 评论

1024
x