字符串哈希

将字符串转化成一个 unsigned long long ，可以实现的时间复杂度查询两个字符串是否相等。

需要先选取一个足够大的质数 ,作为“进制”。当取时，发生哈希碰撞的概率较小。

可以先构造一个数组 ,结合前缀和，可以求出一个字符串的任意字串的哈希值。

C++代码

cpp

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

const int X = 13331;
ull f[500010];

int main()
{
    f[0] = 1;
    for(int i = 1; i < 500010; i++) {
        f[i] = f[i-1] * X;
    }
    return 0;
}

void string_hash(const string &str, vector<ull> &result)
{
    result.resize(str.length());
    result[0] = str[0];
    for(int i = 1; i < str.length(); i++) {
        result[i] = result[i-1] * X + str[i];
    }
}

ull get_hash(const vector<ull> &hash, int left, int right)
{
    if(left == 0) {
        return hash[right];
    }else {
        return hash[right] - hash[left - 1] * f[right - left + 1];
    }
}

首先调用string_hash，得到的结果会储存在result中。然后用get_hash函数得到任意子串的hash值。

字符串哈希 ​

字符串哈希