字符串哈希

Cartis · 2025-05-20 22:39:30 · 算法·理论

字符串哈希

字符串哈希的概念和基本名词

我们先来理解一下有关于字符串哈希的一个概念（也就是字符串哈希到底是个什么？）。

首先，字符串哈希是算法竞赛中用于处理字符串的一个算法，在 S 组（也就是 CSP-S）的比赛中，只需要掌握哈希，字典树，KMP 就可以了，之所以哈希如此重要，是因为许多题目使用哈希会变得简单很多，字符串哈希，就是将一个字符串 s 转化为一个特定的值，从而高效的来完成字符串的匹配或其它操作问题。

接下来我们来了解一下字符串哈希中的几个必要名词：

1. 哈希函数：是指将一个字符串的数据转化位一个整数的一种规则，一个非常好的哈希函数可以尽可能的保证字符串数据和数值的值一一对应。
2. 哈希值：是指一个字符串在哈希函数的转化位得到的值被称为哈希值。
3. 哈希冲突：是指几个不同的字符串数据转化后的哈希值得到的都是一样的，被称之位哈希冲突。

由于哈希冲突会导致我们的代码又可以会出错，接下来我们来找到一些可以避免哈希冲突的一些方法。

1. 工业界常常使用链表来解决此问题，同一个哈希值用一个链表来进行存储。
2. 算法竞赛界常常使用双哈希，即使用两个不同的哈希函数来得到两组哈希值来进行判断，会使得哈希冲突的概率大大降低。

字符串哈希的使用

知道了前面的基本概念，我们来正式地来实现这个哈希的过程。

1. 使用进制哈希作为我们的哈希函数，这个进制数通常选择一个非常偏僻的大质数。

2. 为了放置我们的哈希值进行溢出，我们可以有两种处理方法：

   • 使用取模的方法，通常可以使用取模的方法，这个模数必须很大且是一个质数。
   • 使用自然溢出的方法，因为使用取模虽然也没有问题，但是会导致我们的代码运行效率较慢，所以使用自然溢出的方法会更合适，我们可以直接使用变量类型：unsigned long long 来存储我们的哈希值。

实现的具体操作：

1. 维护一个 unsigned long long 类型的数组 hs，定义 hs_i 表示次字符串前 i 个字符的哈希前缀，注意这里的下标我们通常从 1 开始，所以字符串建议使用字符数组存储。

2. 维护 pw_i 表示 i 个进制数（后面全部称为 base）的乘积，用自然溢出处理。

（注意前面的 hs_i 和 pw_i 前部都是 unsigned long long 类型的变量）。

3. 定义函数 GetHash(l,r) 表示对于此字符串在区间 [l,r] 的子串中，其哈希值为：hs_r - hs_{l-1} \times pw_{r - l + 1}，公式的证明比较简单，这里不再累赘。

4. 定义函数 ReGetHash(l,r,pos) 表示对于字符串在区间 [l,r] 内的字串中，删除单点 pos 的字符后，我们可以得到新的哈希值就是将这个字符串从 pos 的位置进行切割，然后在拼接起来，其公式为：GetHash(l, pos - 1) \times pw_{r - pow} + GetHash(pos + 1, r)。

我来给出以上两个操作的具体代码实现：

ull pw[MAX_N], hs[MAX_N], sub; // 注意是 ull 类型

// 根据上面的公式计算得出

ull get_hs(ull hs[], int l, int r) {
    return hs[r] - hs[l - 1] * pw[r - l + 1];
} 

ull re_hs(ull hs[], int l, int r, int pos) {
    return get_hs(hs, l, pos - 1) * pw[r - pos] +
                          get_hs(hs, pos + 1, r);
}

字符串哈希的例题应用

接下来我们来做几道简单的哈希练手题。

模板题目：P3370 【模板】字符串哈希

思路:

这是一道模板的哈希题目，我们可以直接按照上面的步骤写出代码，我们可以使用一个 set 或者是 map 来存储计算出来的哈希值，因为这道题太过简单，所以训练的价值并不高，所以直接来看代码。

代码：

#include <bits/stdc++.h>

typedef unsigned long long ull;

using namespace std;

const int LEN = 1501;
const int base = 999983;

set<ull> st;
int N, len;
char s[LEN]; // 由于下标是从 1 开始的，所以我们可以直接使用字符数组来存储。
ull hs[LEN], pw[LEN]; // 上面说的哈希数组

int main() {
    cin >> N;
    for (string str; N--;) {
        cin >> s + 1;
        len = strlen(s + 1);
        pw[0] = 1;
        for (int i = 1; i <= len; i++) { // 注意看，这里是所有哈希的必要初始化，以后的代码都会用到这一点。
            pw[i] = pw[i - 1] * base;
            hs[i] = hs[i - 1] * base + s[i];
        }
        st.insert(hs[len]); // 存入 set 中
    }
    cout << st.size() << '\n'; // 直接输出最后的答案即可
    return 0;
}

T1：P10468 兔子与兔子

思路：

这道题其实也是字符串哈希的模板题，每次询问两个区间内的字符串是否是一样的，所以可以使用我们在上面提到的几个函数 get_hs(ull hs[], int l, int r) 函数来实现这个操作。

代码：

#include <bits/stdc++.h>

typedef unsigned long long ull;

using namespace std;

const int LEN = 1e6 + 50;
const int base = 999983;

int len,  Q;
char s[LEN];
ull hs[LEN], pw[LEN];

ull get_hs(ull hs[], int l, int r) {
    return hs[r] - hs[l - 1] * pw[r - l + 1];
} 

int main() {
    cin >> s + 1 >> Q;
    len = strlen(s + 1);
    pw[0] = 1;
    for (int i = 1; i <= len; i++) {
        pw[i] = pw[i - 1] * base;
        hs[i] = hs[i - 1] * base + s[i];
    }
    for (int l1, r1, l2, r2; Q--;) {
        cin >> l1 >> r1 >> l2 >> r2;    
        if (get_hs(hs, l1, r1) == get_hs(hs, l2, r2))
            cout << "Yes\n";
        else 
            cout << "No\n";
    }
    return 0;   
}

T2 : CF39J Spelling Check

思路：

一道一样的模板题，可以发现我们可以直接先预处理两边哈希数组，分别求出两个字符串的哈希数组，然后使用上面说到的 re_hs 函数来直接枚举删除的位置然后判断哈希值是否相等即可。

代码：

#include <bits/stdc++.h>

typedef unsigned long long ull;

using namespace std;

const int LEN = 1e6 + 50;
const int base = 999983;

char s[LEN], str[LEN];
int len;
ull hs[LEN], pw[LEN], hs1[LEN], pw1[LEN];
vector<int> ans;

ull get_hs(ull hs[], int l, int r) {
    return hs[r] - hs[l - 1] * pw[r - l + 1];
}

ull re_hs(ull hs[], int l, int r, int pos) {
    return get_hs(hs, l, pos - 1) * pw[r - pos] + get_hs(hs, pos + 1, r);
}

int main() {
    cin >> s + 1 >> str + 1;
    len = strlen(s + 1);
    pw[0] = 1;
    for (int i = 1; i <= len; i++) {
        pw[i] = pw[i - 1] * base;
        hs[i] = hs[i - 1] * base + s[i];
    }
    pw1[0] = 1;
    for (int i = 1; i <= len - 1; i++) {
        pw1[i] = pw1[i - 1] * base;
        hs1[i] = hs1[i - 1] * base + str[i];
    }
    for (int i = 1; i <= len; i++) {
        if (get_hs(hs1, 1, len - 1) == re_hs(hs, 1, len, i))
            ans.emplace_back(i);
    }
    cout << ans.size() << '\n';
    for (int it : ans)
        cout << it << ' ';
    return 0;   
}

T3：P6739 [BalticOI 2014] Three Friends (Day1)

思路：

这道题其实和上面的题目一样，就是将一个字符串复制了两倍，然后再多增加了一个字符，问最后是否可以还原出一开始的字符串，其实也非常简单，我们可以直接枚举哪一个字符是最后插进去的，然后再通过这个字符的位置来判断原始字符串的位置，通过 re_hs 和 get_hs 直接截取这个最终字符串，然后判断即可，注意这里输出 NOT UNIQUE 的条件是原始字符串不唯一，而不是这个截取的位置不唯一！！！

代码:

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const ull base = 999983;
const int MAX_N = 2e6 + 50;

char s[MAX_N];
int len, ans;
ull pw[MAX_N], hs[MAX_N], sub;

ull get_hs(ull hs[], int l, int r) {
    return hs[r] - hs[l - 1] * pw[r - l + 1];
} 

ull re_hs(ull hs[], int l, int r, int pos) {
    return get_hs(hs, l, pos - 1) * pw[r - pos] + get_hs(hs, pos + 1, r);
}

int main() {
    cin >> len >> s + 1;
    if (len % 2 == 0) {
        cout << "NOT POSSIBLE";
        return 0;
    }
    pw[0] = 1;
    for (int i = 1; i <= len; i++) {
        pw[i] = pw[i - 1] * base;
        hs[i] = hs[i - 1] * base + s[i];
    }
    for (int i = 1; i <= len; i++) {
        ull t1, t2;
        if (i <= len / 2)
            t1 = re_hs(hs, 1, len / 2 + 1, i);
        else
            t1 = get_hs(hs, 1, len / 2);
        if (i >= (len + 3) / 2)
            t2 = re_hs(hs, (len + 1) / 2, len, i);
        else
            t2 = get_hs(hs, (len + 3) / 2, len);
        if (t1 == t2) {
            if (ans && sub != t1) {
                cout << "NOT UNIQUE";
                return 0;
            }
            ans = i, sub = t1;
        }
    }
    if (ans == 0) {
        cout << "NOT POSSIBLE";
        return 0;
    }
    for (int i = 1; i <= len / 2 + (ans <= len / 2); i++) {
        if (i != ans)
            cout << s[i];
    }
    return 0;
}