|
|
| 第1行： |
第1行： |
| == 一些好用的语法知识 ==
| | #REDIRECT [[06-数学相关/05-字符串哈希]] |
| | | [[Category:三三文档]] |
| * [http://cpp.33dai.cn/reference/zh/cpp/string/basic_string/substr.html s.substr(pos, count)]
| |
| ** 返回子串 [pos, pos+count) 。若请求的字串越过字符串的结尾，即 count 大于 size() - pos （例如若 count == npos ），则返回的子串为 [pos, size()) 。
| |
| ** 可以不写第二个参数，<code>s.substr(pos)</code> 会返回子串 [pos, size())。
| |
| * 【C++11起】：[http://cpp.33dai.cn/reference/zh/cpp/container/unordered_set.html unordered_set<T>]：<code>insert</code> 时会把 T 类型元素哈希后放入集合，搜索、插入和移除拥有平均常数时间复杂度。
| |
| * 【C++11起】：[http://cpp.33dai.cn/reference/zh/cpp/container/unordered_map.html unordered_map<T,T>]：略
| |
| | |
| == 哈希基础 ==
| |
| | |
| === 整串哈希到整数 - 单哈希 ===
| |
| | |
| <syntaxhighlight lang="cpp">
| |
| 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;
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| === 整串哈希到整数 - 双哈希 ===
| |
| | |
| <syntaxhighlight lang="cpp">
| |
| 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);
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| === 整串哈希到整数 - 自然溢出哈希 ===
| |
| | |
| <syntaxhighlight lang="cpp">
| |
| 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;
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| === 子串哈希 ===
| |
| | |
| <syntaxhighlight lang="cpp">
| |
| // 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;
| |
| }
| |
| }
| |
| // 获取 s[l]~s[r] 的哈希值
| |
| int getHash(int l, int r)
| |
| {
| |
| return (myHash[r] - myHash[l - 1] * powP[r - l + 1] % MOD + MOD) % MOD;
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| == 循环节判断 ==
| |
| | |
| 如果 <code>s[1 ~ n-len] == s[len+1 ~ n]</code>，那么 <code>s[1~len]</code> 是一个循环节。
| |