33DAI：导入1个版本

2026-05-20T18:12:11Z

导入1个版本

←上一版本		2026年5月20日 (三) 18:12的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:50:33Z

批量导入三三文档

←上一版本		2026年5月20日 (三) 16:50的版本
（没有差异）

33DAI：导入1个版本

2026-05-20T16:25:42Z

导入1个版本

←上一版本		2026年5月20日 (三) 16:25的版本
（没有差异）

->Importer：批量导入三三文档

2026-05-20T16:22:29Z

批量导入三三文档

新页面

== 整串哈希 ==

=== 单哈希 ===

<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, hash2 = 0;
for (int i = 0; i < s.length(); i++)
{
hash1 = (hash1 * P1 + s[i]) % MOD1;
hash2 = (hash2 * P2 + s[i]) % MOD2;
}
return {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]; // 自动对 2^64 取模
return hash;
}
</syntaxhighlight>

== 子串哈希 ==

通过预处理前缀哈希，可以在 <math>O(1)</math> 时间内获取任意子串的哈希值。

<syntaxhighlight lang="cpp">
string s; // s[1]~s[n]
const long long MOD = 1000000007;
const int P = 29;
long long myHash[30005];
long long powP[30005];

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> 是一个循环节。

可以用子串哈希快速判断两个子串是否相等。

== 字符串去重 ==

<syntaxhighlight lang="cpp">
unordered_set<unsigned long long> hashes;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
hashes.insert(getHash(s));
}
cout << hashes.size(); // 不同字符串的数量
</syntaxhighlight>

[[Category:数学相关]]
[[Category:三三文档]]

06-数学相关/05-字符串哈希 - 版本历史

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：​导入1个版本

->Importer：​批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档

33DAI：导入1个版本

->Importer：批量导入三三文档