算法竞赛进阶指南 基本数据结构 0x14哈希表

Hash表

Hash表又称散列表，一般由Hash函数（散列函数）与链表结构共同实现。与离散化思想类似。

解决冲突：有一种称为“开散列”的解决方案是，建立一个邻接表结构，以Hash函数的值域作为表头数组head，映射后的值相同的原始信息被分为同一类，构成一个链表接在对应的表头之后，链表的节点上可以保存原始信息和一些统计数据。

设计Hash函数为$H(x)=(x\mathrm{mod}P)+1$，其中P是一个比较大的质数，但不超过N。显然，这个Hash函数把数列A分成P类，我们可以依次考虑数列中的每个数A[i]，定位到head[A[i]]这个表头所指向的链表。如果该链表中不包含A[i]，我们就在表头后插入一个新节点A[i]，并在该节点上记录A[i]出现了1次，否则我们就直接找到已经存在的A[i]节点将其出现次数加1。因为整数序列A是随机的，所以最终所有A[i]会比较均匀地分散在各个表头之后。

对于非随机的数列，我们可以设计更好的Hash函数来保证其时间复杂度。

同样地，如果我们需要维护的是比大整数复杂得多的信息的某些性质（如是否存在、出现次数等），也可以用Hash表来解决。字符串就是一种比较一般化的信息。

0、AcWing 137. 雪花雪花雪花

题意 ：

• 有 N 片雪花，每片雪花由六个角组成，每个角都有长度。
• 第 i 片雪花六个角的长度从某个角开始顺时针依次记为 ai,1,ai,2,…,ai,6。
• 因为雪花的形状是封闭的环形，所以从任何一个角开始顺时针或逆时针往后记录长度，得到的六元组都代表形状相同的雪花。
• 我们称两片雪花形状相同，当且仅当它们各自从某一角开始顺时针或逆时针记录长度，能得到两个相同的六元组。
• 求这 N 片雪花中是否存在两片形状相同的雪花。
• 1≤N≤100000,

思路 ：

• 定义Hash函数$H(a_{i,1},a_{i,2},...,a_{i,6})=({\sum }_{j=1}^6{a}_{i,j}+{\prod }_{j=1}^6{a}_{i,j})\mathrm{mod}P$，其中/P是我们自己选取的一个较大的质数。显然，对于两片形状相同的雪花，它们六个角的长度之和、长度之积都相等，因此它们的Hash函数值也相等。
• 建立一个Hash表，把N片雪花依次插入。对于每片雪花$a_{i,1},a_{i,2},...,a_{i,6}$，我们直接扫描表头$H(a_{i,1},a_{i,2},...,a_{i,6})$对应的链表，检查是否存在与a_{i,1},a_{i,2},…,a_{i,6}形状相同的雪花即可。
• 对于随机数据，期望的时间复杂度为$O(\frac{N^2}{P})$；取P为最接近N的质数，期望的时间复杂度为$O(N)$。
• 在下一节中，我们将学习循环同构串的“最小表示法”，进一步提高判断两片雪花形状是否相同的效率。
• 注意6 * sizeof(int) 不要写成 sizeof a，因为，我们定义的a数组有10个长度

#include 
#include 
using namespace std;
const int N = 1e5 + 10, P = 99991;

int n;
int head[N], ne[N], tot, snow[N][6];

int H(int *a) {
    int sum = 0, mul = 1;
    for (int i = 0; i < 6; ++ i) {
        sum = (sum + a[i]) % P;
        mul = (long long)mul * a[i] % P;
    }
    return (sum + mul) % P;
}
bool equal(int *a, int *b) {
    for (int i = 0; i < 6; ++ i) {
        for (int j = 0; j < 6; ++ j) {
            bool eq = 1;
            for (int k = 0; k < 6; ++ k) {
                if (a[(i + k) % 6] != b[(j + k) % 6]) eq = 0;
            }
            if (eq) return 1;
            eq = 1;
            for (int k = 0; k < 6; ++ k) {
                if (a[(i + k) % 6] != b[(j - k + 6) % 6]) eq = 0;
            }
            if (eq) return 1;
        }
    }
    return 0;
}
bool insert(int *a) {
    int val = H(a);
    for (int i = head[val]; i; i = ne[i]) {
        if (equal(snow[i], a)) return 1;
    }
    ++ tot;
    memcpy(snow[tot], a, 6 * sizeof(int));
    ne[tot] = head[val];
    head[val] = tot;
    return 0;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i) {
        int a[10];
        for (int j = 0; j < 6; ++ j) scanf("%d", &a[j]);
        if (insert(a)) {
            puts("Twin snowflakes found.");
            return 0;
        }
    }
    puts("No two snowflakes are alike.");
}

字符串Hash

下面介绍的字符串Hash函数把一个任意长度的字符串映射成一个非负整数，并且其冲突概率几乎为零。

取一固定值P，把字符串看作P进制数，并分配一个大于0的数值，代表每种字符。一般来说，我们分配的数值都远小于P。例如，对于小写字母构成的字符串，可以令a = 1，b = 2，…，z = 26。取一固定值M，求出该P进制数对M的余数，作为该字符串的Hash值（->(P进制数->取模))。

一般来说，我们取 P = 131 或 P = 13331，此时Hash值产生冲突的概率极低，只要Hash值相同，我们就可以认为原字符串是相等的。通常我们取M = 2^{64}，即直接使用unsigned long long类型存储这个Hash值，在计算时不处理算术溢出问题，产生溢出时相当于自动对$2^{64}$取模，这样可以避免低效的取模（mod）运算。

除了在极特殊构造的数据上，上述Hash算法很难产生冲突，一般情况下上述Hash算法完全可以出现在题目的标准解答中。我们还可以多取一些恰当的P和M的值（例如大质数），多进行几组Hash运算，当结果都相同时才认为原字符串相等，就更加难以构造出使这个Hash产生错误的数据。

对字符串的各种操作，都可以直接对P进制数进行算术运算反映到Hash值上。

如果我们已知字符串S的Hash值为H(S)，那么在S后添加一个字符串构成的新字符串S+c的Hash值就是H(S+c)=(H(s) * P + value[c]) mod M。其中，乘P就相当于P进制下的左移运算，value[c]是我们为c选定的代表数值

如果我们已知字符串S的Hash值为H(S)，字符串S+T的Hash值为H(S+T)，那么字符串T的Hash值H(T) = (H(S+T) - H(S) * $P^{length(T)}$) mod M。

通过上面两种操作，我们可以通过O(N)的时间预处理字符串所有前缀Hash值，并在O(1)的时间内查询它的任意子串的Hash值。

0、AcWing 138. 兔子与兔子

题意 ：

• 我们首先选取一个好长好长的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 个小写英文字母）。
• 然后我们每次选择两个区间，询问如果用两个区间里的 DNA 序列分别生产出来两只兔子，这两个兔子是否一模一样。
• 注意两个兔子一模一样只可能是他们的 DNA 序列一模一样。
• 1≤length(S),m≤1000000

#include 
#include  // strlen的头文件
using namespace std;
typedef unsigned long long ULL; // ULL
const int N = 1e6 + 10, P = 131; // P可以是int

char str[N]; // char数组的方式
ULL h[N], power[N]; // h和power都是ULL

ULL get(int l, int r) {
    return h[r] - h[l - 1] * power[r - l + 1]; // 公式
}

int main() {
    scanf("%s", str + 1); // 输入char数组，注意下标从1开始
    int n = strlen(str + 1); // 得到char数组长度
    power[0] = 1; // 注意乘法数组初始化！
    for (int i = 1; i <= n; ++ i) {
        h[i] = h[i - 1] * P + str[i] - 'a' + 1; // 最后+1，因为否则a就是0了
        power[i] = power[i - 1] * P;
    }
    int m;
    scanf("%d", &m);
    while (m -- ) {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
}

1、AcWing 139. 回文子串的最大长度

题意 ：

• 给定一个长度为 N 的字符串 S，求他的最长回文子串的长度是多少。
• 输入将包含最多 30 个测试用例，每个测试用例占一行，以最多 1000000 个小写字符的形式给出。
• 输入以一个以字符串 END 开头的行表示输入终止。

思路 ：

• 我们发现回文串分为两类：奇回文串、偶回文串
• 于是在本题中，我们可以枚举回文子串的中心位置i=1～N，看从这个中心位置出发向左右两侧最长可以扩展出多长的回文串，也就是说：
  1、求出一个最大的整数p，使得S[i-p ~ i] = reverse(S[i ~ i+p])，那么以i为中心的最长奇回文子串的长度就是2p+1
  2、求出一个最大的整数q，使得S[i-q ~ i-1] = reverse(S[i ~ i+q-1])，那么以i-1和i之间的夹缝为中心的最长偶回文子串的长度就是2q
• 根据上一题，我们已知在O(N)预处理前缀Hash值后，可以O(1)计算任意字串的Hash值；类似地，我们可以倒着做一遍预处理，就可以O(1)计算任意字串倒着读的Hash值
• 于是我们可以对p和q进行二分答案，用Hash值O(1)比较一个正着读的字串和一个倒着读的字串是否相等，从而在O(logN)的时间内求出最大的p和q
• 因此，总的时间复杂度就是O(NlogN)
• 这里有一个小技巧，在每个字符前添加一个非字母的字符，假设为#，比如 abc 被扩展成 #a#b#c，这样的话，得到所有回文字串必然是奇数长度的。那么我们就可以直接遍历每个字符，尝试以所有字符为对称中心（这样就不需要考虑夹缝的情况了）的回文串最大长度可能是多少
• 可以发现，当回文串最左边的字符是#时(#a#a#)，实际回文串的长度就是填充后对称中心左边子串的长度；而当回文串最左边的字符是字母时(a#b#a)，实际回文串的长度就是填充后对称中心左边子串的长度+1
• 有一个名为Manacher的算法可以O(N)求解该问题，感兴趣的读者可以自行查阅相关资料

#include 
#include 
using namespace std;
typedef unsigned long long ull;
const int N = 2e6 + 10, P = 131;

char s[N];
ull h1[N], h2[N], p[N];

ull get(ull h[], int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    int cnt = 0;
    while (scanf("%s", s + 1) && strcmp(s + 1, "END")) {
        int n = strlen(s + 1) * 2;
        for (int i = n; i; i -= 2) {
            s[i] = s[i / 2];
            s[i - 1] = 'z' + 1;
        }
        p[0] = 1ull;
        for (int i = 1, j = n; i <= n; ++ i, -- j) {
            h1[i] = h1[i - 1] * P + s[i] - 'a' + 1;
            h2[i] = h2[i - 1] * P + s[j] - 'a' + 1;
            p[i] = p[i - 1] * P;
        }
        int ans = 0;
        for (int i = 1; i <= n; ++ i) {
            int l = 0, r = min(i - 1, n - i);
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (get(h1, i - mid, i - 1) == get(h2, n + 1 - (i + mid), n + 1 - (i + 1))) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            if (s[i - l] <= 'z') {
                ans = max(ans, l + 1);
            } else {
                ans = max(ans, l);
            }
        }
        printf("Case %d: %d\n", ++ cnt, ans);
    }
}

（Skip）2、后缀数组