hash在ACM种的应用

acm

Hash

有时候我们要统计很大的数的个数时，但是这个时候我们又开不下这么大的数组，我们常常可以借助map，或者hash_table之类的工具。

Hash 统计数字个数

有时候map占用的数据也非常大， 我们可以利用链式前向星来代替链表实现一个简易的hash来统计每个数的个数，这个所占用的空间比map要小的多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int mod=1<<15;
struct Edge{int v,nxt,w;}e[mod];
int head[mod], cnt;
void init(){ memset(head, -1, sizeof head); cnt = 0; }

int gethash(int x){ // 将数字hash
    return (x+ mod) & (mod-1);
}

void insert(int x) { // 插入
    int id=gethash(x); // 得到hash值
    for(int i=head[id]; i != -1;i=e[i].nxt) { // 便利冲突的元素
        if(e[i].v==x) { e[i].w++; return; }
    } e[cnt] = {x, head[id], 1}; head[id]=cnt++; // 新元素额外添加
}

void search(int x) { // 查找个数
    int id=gethash(x);
    for(int i=head[id] ; i!=-1;i=e[i].nxt) {
        if(e[i].v==x) return e[i].w;
    } return 0;
}

统计字符串

如果我们就考虑小写字母的话，那么有26种小写字母，那么对于1e6长度的字符串，就有$10^{1414973}$ 多种情况，而对于我们所要处理的字符串实在是太少，所以我们对于字符串hash很少来处理冲突，如果发现确实有冲突，那么我们可以采用使用两种不同的hash来降低同时冲突的概率。

一般我们对于字符串是如此hash的：

比如有一个字符串abc

我们构造一个函数：$f(x) = a[0]x^{n-1} + a[1]x^{n-2} + … + a[n-1] $

x就是我们自己选取的数，一般常用一个质数，比如131，233之类的也用字母种类数比如26之类的。

那么对于上面这个字符串$f(26) = ax^{2} + bx^{2} + c $

a,b,c的值可以是1,2,3或者是他们本身的ASCII值。

使用这种方式的好处就是一次O(n)的预处理后可以O(1)查询任意字串的值，除此之外还有滚动哈希之类的操作.

POJ - 1200 子串种类

题意: 给定一个字符串s, 查询长度为m的子串一共有多少种.

滚动hash

滚动hash其实就是我们先计算第一个长度为m的字符串的hash值,我们去计算第二个长度为m的子串时,我们只需要使用上一个hash值减去其第一个字母的影响然后乘x再加上后面缺少的那个字母的值. 举例如下

$f(x) = a[0]x^{n-1} + a[1]x^{n-2} + … + a[n-1] $ , 我们先减去 $a[0] * x^{n-1} $ 然后整体乘x , 最后加上a[n].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstring>
const int N = 1.6e7+9;
using namespace std;
char s[N];
bool has[N], vis[256];
int n, nc, a[256], m, cnt;

int main(){
    scanf("%d%*d%s",&m,s); n = strlen(s);
    for (int i = 0; i < n; i++) {
        if(!vis[s[i]]) {
            vis[s[i]] = 1; a[s[i]]=nc++; // 对于字母出现的顺序来决定大小
        }
    } int ans = 0, x = 0, y = 1;
    for (int i = 0; i < m; i ++) {
        x = x*nc + a[s[i]];         // 计算第一个长度为m的字符串的hash值
        y *= nc;
    } y/= nc; has[x] = 1; ans ++; // y = nc^{m-1}
    for (int i = 1; i <= n-m; i++) {
        x = (x - a[s[i-1]]*y) * nc + a[s[i+m-1]]; // 滚动hash
        if(!has[x]) has[x] = 1, ans++;
    } return printf("%d\n", ans), 0;
}

O(n) 预处理后整体查询

由于map的速度实在是太慢了,而且占用空间也大,我们使用之前自己写的.

这里我们o(n)预处理的h(i) 代表的是 以i为结尾的 字串的hash值. bit则存放的是x^i, 那么我们想要得到一个字串(l,r)的值的话我们对于0-r的字串的值减去前0-(l-1) 的字串的影响就行了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <map>
#include <cstring>
#define ull unsigned long long
const int base = 1e9+9;
const int N = 2e6+9;
using namespace std;
int n, m;
ull bit[N], h[N];
char s[N];

const int mod=1<<15;
struct Edge{int v,nxt,w;}e[mod];
int head[mod], cnt;
void init(){memset(head, -1, sizeof head); cnt = 0;}
int gethash(int x){return (x+ mod) & (mod-1);}
void insert(int x) {
    int id=gethash(x); 
    for(int i=head[id]; i != -1;i=e[i].nxt) {
        if(e[i].v==x) { e[i].w++; return;}
    } e[cnt].v = x; e[cnt].nxt = head[id]; e[cnt].w = 1; head[id]=cnt++;
}

int main(){
    memset(head, -1, sizeof head);    // 初始化
    scanf("%d%*d%s", &m, s+1); bit[0] = 1; n = strlen(s+1);
    for (int i = 1; i < N; i++) bit[i] = bit[i-1]*base;      // x^i
    for (int i = 1; i <= n; i++) h[i] = h[i-1]*base + s[i];  // 以i为结尾的 字串的hash值
    for (int i = m; i <= n; i++) {
        ull tmp = (h[i] - h[i-m]*bit[m]);                    // i-m+1, i 字串的hash值
        insert(tmp);
    } printf("%d\n", cnt);
    return 0;
}

二维字符矩阵

题意: 给出一个n * m的矩阵。让你从中发现一个最大的正方形。使得这样子的正方形在矩阵中出现了至少两次。输出最大正方形的边长。

$$
f(x, y ) = a[0][0] x^{m-1} y^{n-1} + a[0][1] x^{m-2}y^{n-1} + … + a[0][m-1]y^{n-1} \
\ \ \ \ \ \ \ \ \ \ \ \ + a[1][0] x^{m-1} y^{n-2} + a[1][1] x^{m-2}y^{n-2} + … + a[1][m-1]y^{n-2} \

  • … \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
    \ + a[n-1][0] x^{m-1} + a[n-1][1] x^{m-2} + … + a[n-1][m-1]
    $$

这样下来我们如果要计算一个左上角(l1, r1) ,右下角为(l2, r2)的字符矩阵的hash值就方便的多了.

这个计算方法和二维前缀和有点类似, 使用整个矩阵减去两块绿色的影响就是了。

如果x边长的正方形矩阵满足题意,那么1- (x-1)边长的正方形矩阵都满足,所以具有二分性质,我们可以使用二分来枚举边长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>

using namespace std;
using ull = unsigned long long;
const int N = 555;
const int mod = 1e5+7;
struct Edge { ull v; int nxt; }e[N*N];
int head[mod];
ull base1 = 1313, base2 =13131;
ull has1[N][N], has2[N][N], bit1[N], bit2[N];
char s[N][N];
int n, m, cnt;

void init(){    // 初始化
    bit1[0] = bit2[0] = 1; cnt = 0;
    for (int i = 1; i < N; i++) {
        bit1[i] = bit1[i-1]*base1;
        bit2[i] = bit2[i-1]*base2;
    } for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            has1[i][j] = has1[i][j-1]*base1+s[i][j]; // 计算的是i行的以j为末尾的字符串的hash值
            has2[i][j] = has2[i-1][j]*base2+has1[i][j]; // 计算1-i, 1-j 的矩阵的hash值
        }
    }
}

void inser(int u, ull v){ e[cnt].v = v; e[cnt].nxt = head[u]; head[u] = cnt++;}

ull cal(int i, int j, int x){  // 计算 (i,j) (i+x-1, j+x-1) 矩阵的hash值
    ull ret = has2[i+x-1][j+x-1];    
    ret -= has2[i+x-1][j-1] * bit1[x] + has2[i-1][j+x-1]*bit2[x];
    ret += has2[i-1][j-1] * bit1[x] * bit2[x];
    return ret;
}

bool sech(ull x){
    int t = x % mod;
    for (int i = head[t]; ~i; i = e[i].nxt) {
        if(e[i].v == x) return 1;
    } return 0;
}

bool check(int x){  // 判断是否存在满足题意的 x长度的边长的矩阵
    cnt = 0; memset(head, -1, sizeof head); // 清空hash表种的元素
    for (int i = 1; i+x-1 <= n; i++) {
        for (int j = 1; j+x-1 <= m; j++) {
            ull t = cal(i, j, x); // 每次计算一个矩阵
            if(sech(t)) return 1; // 查询是否有同样的矩阵
            inser(t%mod, t);      // 没有就将矩阵的hash值插入
        }
    } return 0;
}

int main() {
    scanf("%d%d", &n, &m);  
    for (int i = 1; i <= n; i++) {
        scanf("%s", s[i]+1);
    } init(); int l = 1, r = min(m, n); 
    while(l <= r){      // 二分边长
        int mid = (l+r)>>1;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    } return printf("%d\n", l-1), 0;
}

最小表示法

求字符串的循环表示法：

我们有一个字符串s,我们可以不停的把头上的字母放在尾巴上这样就构成一个循环串s[k],s[k+1],s[k+2],..,s[n],s[1],..,s[k-1]; 我们可以得到n个循环串，我们要去寻找字典序最小的串的首字母的原始下标。

我们可以使用双指针法，可以做到O(n)， 也可以利用hash和二分算法不过这个复杂度是O(nlogn)的；

双指针法

1
2
3
4
5
6
7
8
9
10
11
int getMi(){
    int i = 0, j = 1, l; // i,j 就是需要比较的两个循环串的首字母下标，l是长度
    while(i < n && j < n){
        for(l = 0; l < n; l++){
            if(s[(i+l)%n] != s[(j+l)%n]) break;  // 找到第一个不相等的。
        } if(l >= n) break; // 没找到说明两个循环串相等
        if(s[(i+l)%n] < s[(j+l)%n]) j += l+1; // 如果i串更小，那么j移动l+1位,这里改成>就是字典序最大
        else i += l+1;                        // 否则i串移动l+1位
        if(i==j) j++;    // 如果i==j了让j往后移动一格
    } return i<j?i:j;   // 返回下标小的(此时要么有一个>n或者i,j串相等)
}

二分+ Hash

hash的做法是n个字符串我们从第一个开始比较，始终维护最小的循环串，比较字符串是log(n)比较的，方法是二分到两个字符串第一个不同的位置。所以总体复杂度是O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const int N = 1e5+9;
const int base = 131;
int n;
char s[N];
ull bit[N], has[N];

bool check(int x, int y, int l){ // 判断x,y开始l长度的字符串是否相等
    ull u = has[x+l-1] - has[x-1]*bit[l];
    ull v = has[y+l-1] - has[y-1]*bit[l];
    return u == v;
}

bool ok(int x, int y){ // 比较那个下标开始的串更小
    int l = 0, r = n;
    while(l <= r) {
        int mid = (l+r) >> 1;
        if(check(x, y, mid)) l = mid + 1;
        else r = mid - 1;
    } if(l-1==n) return 0;
    return (s[x+l-1]) < (s[y+l-1]);
}

int main() {
    scanf("%s", s+1); bit[0] = 1; n = strlen(s+1);
    for (int i = 1; i <= n; i++) s[i+n] = s[i];
    for (int i = 1; i < N; i++) bit[i] = bit[i-1]*base;
    for (int i = 1; i <= n*2; i++) has[i] = has[i-1]*base + s[i];
    int x = 1;
    for (int i = 2; i <= n; i++) {
        if(ok(i, x)) x = i;
    } return printf("%d\n", x), 0;
}

本文标题:hash在ACM种的应用

文章作者:呼哧

发布时间:2018-08-04, 04:06:58

最后更新:2018-10-10, 23:29:05

原始链接:http://hu-chi.github.io/2018/08/04/acm/hash/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. Hash
    1. 1.1. Hash 统计数字个数
    2. 1.2. 统计字符串
      1. 1.2.1. POJ - 1200 子串种类
        1. 1.2.1.1. 滚动hash
        2. 1.2.1.2. O(n) 预处理后整体查询
      2. 1.2.2. 二维字符矩阵
    3. 1.3. 最小表示法
      1. 1.3.1. 双指针法
      2. 1.3.2. 二分+ Hash
|