字符串哈希

一些好用的语法知识

• s.substr(pos, count)
  • 返回子串 [pos, pos+count) 。若请求的字串越过字符串的结尾，即 count 大于 size() - pos （例如若 count == npos ），则返回的子串为 [pos, size()) 。
  • 可以不写第二个参数，s.substr(pos) 会返回子串 [pos, size())。
• 【C++11起】：unordered_set<T>：insert 时会把 T 类型元素哈希后放入集合，搜索、插入和移除拥有平均常数时间复杂度。
• 【C++11起】：unordered_map<T,T>：略

哈希基础

整串哈希到整数 - 单哈希

const long long MOD = 1000000007;
const int P = 29;
long long getHash(const string &s)
{
    long long hash = 0;
    for (int i = 0; i < s.length(); i++)
        hash = (hash * P + s[i]) % MOD;
    return hash;
}

整串哈希到整数 - 双哈希

const long long MOD1 = 1000000007, MOD2 = 998244353;
const int P1 = 29, P2 = 31;
pair<long long, long long> getHash(const string &s)
{
    long long hash1 = 0;
    long long hash2 = 0;
    for (int i = 0; i < s.length(); i++)
    {
        hash1 = (hash1 * P1 + s[i]) % MOD1;
        hash2 = (hash2 * P2 + s[i]) % MOD2;
    }
    return make_pair(hash1, hash2);
}

整串哈希到整数 - 自然溢出哈希

const int P = 29;
unsigned long long getHash(const string &s)
{
    unsigned long long hash = 0;
    for (int i = 0; i < s.length(); i++)
        hash = hash * P + s[i];
    return hash;
}

子串哈希

// Hash
string s;
const long long MOD = 1000000007;
const int P = 29;
long long myHash[30005];
long long powP[30005];
// 初始化 s[1]~s[n] 的前缀哈希
void initHash(int n)
{
    powP[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        myHash[i] = (myHash[i - 1] * P + s[i] - 'a' + 1) % MOD;
        powP[i] = powP[i - 1] * P % MOD;
    }
    powP[n + 1] = powP[n] * P % MOD;
}
// 获取 s[l]~s[r] 的哈希值
int getHash(int l, int r)
{
    return (myHash[r] - myHash[l - 1] * powP[r - l + 1] % MOD + MOD) % MOD;
}

循环节判断

如果 s[1 ~ n-len] == s[len+1 ~ n]，那么 s[1~len] 是一个循环节。