s.substr(pos) 会返回子串 [pos, size())。insert 时会把 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] 是一个循环节。