题解：P3370 【模板】字符串哈希

· · 题解

这里提供 XorShift 哈希方式。

我们考虑哈希字符串的形态，不难想到，前 i 位形成的前缀的哈希值可以由前 i-1 位形成的前缀的哈希值和第 i 位字符转移得来，这也是大多数字符串哈希的哈希思路。

我们会考虑对 hsh_{i-1} 进行一次映射，然后再更新上这一位的字符串。以常规的“把字符串看作高进制数来说”，我们会把 hsh_{i-1} 乘上一个高进制，这就是一种映射。

但多项式映射的冲突率是很高的。所以这里提供一种冲突率极低的方式，也就是 XorShift。

事实上，这是一个伪随机数生成算法。我们可以利用其周期长的特性进行映射。

关于那三次位移的常量，实测换成别的也够用，但是用这个经典的常量好背好写可以获得更大的周期，也就是更小的冲突率。

const ull mask=mt19937_64(time(0))();
ull shift(ull x){
    x^=mask;
    x^=x<<13;
    x^=x>>17;
    x^=x<<5;
    x^=mask;
    return x;
}

其实那两次对随机常量 mask 的异或可有可无，但为了防止被人对着 Hack，所以可以加上。事实上我不是很确定这道题的数据范围能不能卡掉。但这并没有很大的常数影响，所以为了保险就加上吧。

然后是关键部分代码：

const ull mask=mt19937_64(time(0))();
ull shift(ull x){
    x^=mask;
    x^=x<<13;
    x^=x>>17;
    x^=x<<5;
    x^=mask;
    return x;
}

set<ull> hshs;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;cin>>n;
    string s;
    rep(i,1,n){
        cin>>s;
        ull hsh=0;
        for(auto c:s)hsh=shift(hsh)+c;
        hshs.insert(hsh);
    }
    cout<<hshs.size();
    return 0;
}

代码中对当前位的更新使用了直接加的方式，事实上直接异或也没有问题，以及别的杂七杂八的更新方法多半都没有问题，是自由的。