字符串哈希学习笔记

OP：哇 好难懂 谁发明了这恶心的算法。。。

字符串哈希

  • 1.字符串哈希作用
    • 将字符串计算为一个整数。
    • 要求： 不同的字符串映射为不同的值，同一个字符串映射为相同的值。
  • 2.如何计算字符串的哈希值
    • 将字符串视为P进制的数字，经验上 P=131、13331P=131、13331 .
    • 如果字符串仅包含大写、小写、数字字符其中之一，比如：a...za...z，将其映射为 1..261..26。
    • 一定不能将字符映射为 00 。
  • 3.计算出来的结果太大，将结果 %h。(h=264)\%h。(h=2^{64})
    • %h 的方法：将计算结果直接赋值给 unsigned long longunsigned\ long\ long .
  • 4.如何计算区间哈希值：利用滚动(前缀)哈希值，计算区间哈希值。
    • 前缀哈希值：h[i]=h[i−1]∗P+(s[i]−′a′+1)h[i]=h[i-1]*P+(s[i]-'a'+1)
    • 区间哈希值：h[L，R]=h[R]−h[L−1]∗P(R−L+1)h[L，R]=h[R]-h[L-1]*P^(R-L+1)

习题

额。。。（汗流浃背

01 子串判重

解法：套模版，求区间哈希值直接使用前缀和（官方叫做滚动哈希值）

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
#include <bits/stdc++.h>
using namespace std;

unsigned long long h[1000100], p[1000100];
char s[1000100];
void shash() {
    int n = strlen(s + 1);
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * 131 + (s[i] - 'a' + 1);
        p[i] = p[i - 1] * 131;
    }
}
unsigned long long get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
    scanf("%s", s + 1);
    shash();
    int n;
    cin >> n;
    while (n--) {
        int l, r, x, y;
        scanf("%d%d%d%d", &l, &r, &x, &y);
        if (get(l, r) == get(x, y))
            puts("Yes");
        else
            puts("No");
    }
}

02 前缀和后缀

解法：套模版，暴力枚举每个前缀，如果它的滚动哈希值与给定串的相同长度后缀的滚动哈希值相同，那么就代表这个串既是前缀也是后缀。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 400100;
const int P = 131;
typedef unsigned long long ull;
ull h[N], p[N];
int n;
char s[N];
void gethash() {
    int len = strlen(s + 1);
    p[0] = 1;
    for (int i = 1; i <= len; i++) {
        h[i] = h[i - 1] * P + (s[i] - 'a' + 1);
        p[i] = p[i - 1] * P;
    }
}
ull get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
    while (scanf("%s", s + 1) != EOF) {
        gethash();
        int siz = strlen(s + 1);
        for (int i = 1; i <= siz; i++) {
            if (get(1, i) == get(siz - i + 1, siz)) {
                printf("%d ", i);
            }
        }
        puts("");
    }
}

03 最多子串重复次数

解法

  • 枚举子串长度 1−n1-n ,对于每个长度为 ii 的子串，计算 hash[1,n−i]==hash[i+1,n]hash[1,n-i]==hash[i+1,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
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull h[1000010], p[1000100];
const int P = 131;
char s[1000010];
int ans;
void gethash() {
    int len = strlen(s + 1);
    p[0] = 1;
    for (int i = 1; i <= len; i++) {
        h[i] = h[i - 1] * P + (s[i] - 'a' + 1);
        p[i] = p[i - 1] * P;
    }
}
ull get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
    while (scanf("%s", s + 1) and s[1] != '.') {
        gethash();
        int len = strlen(s + 1);
        for (int i = 1; i <= len; i++) {
            if (len % i == 0) {
                if (get(1, len - i) == get(i + 1, len)) {
                    printf("%d\n", len / i);
                    break;
                }
            }
        }
    }
}

04 三个火枪手

解法

  • 用unordered_set，将删除第 ii 个字符之后，如果合法，那就将剩余字符串存到unordered_set里面，如果中途存储的结果超过1个，那就输出NOT UNIQUE。如果都是零，那就NOT POSSIBLE。
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
65
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
const int P = 131;
set<unsigned long long> st;
typedef unsigned long long ull;
ull h[N], p[N];
char s[N];
void gethash() {
    int len = strlen(s + 1);
    p[0] = 1;
    for (int i = 1; i <= len; i++) {
        p[i] = p[i - 1] * P;
        h[i] = h[i - 1] * P + (s[i] - 'A' + 1);
    }
}
ull get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
    int len;
    scanf("%d%s", &len, s + 1);
    gethash();
    int mid = len / 2 + 1;
    ull l, r;
    char res = ' ';
    for (int i = 1; i <= len; i++) {
        if (i == 1) {
            l = get(2, mid);
            r = get(mid + 1, len);
        } else if (i == len) {
            l = get(1, mid - 1);
            r = get(mid, len - 1);
        } else if (i < mid) {
            l = get(1, i - 1) * p[mid - i] + get(i + 1, mid);
            r = get(mid + 1, len);
        } else if (i > mid) {
            l = get(1, mid - 1);
            r = get(mid, i - 1) * p[len - i] + get(i + 1, len);
        } else if (i == mid) {
            l = get(1, mid - 1);
            r = get(mid + 1, len);
        }
        if (l == r) {
            st.insert(l);
            if (st.size() > 1) {
                puts("NOT UNIQUE");
                return 0;
            }
            if (i <= mid)
                res = 'R';
            else
                res = 'L';
        }
    }
    if (st.size() == 0)
        puts("NOT POSSIBLE");
    else {
        s[mid] = '\0';  // 输出到这里的时候就停止输出
        if (res == 'L')
            printf("%s", s + 1);
        else
            printf("%s", s + mid + 1);
    }
}

05 字符串匹配

思路：

  • 枚举主串所有字符能否和模式串匹配。
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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int P = 131;
typedef unsigned long long ull;
ull h[N], p[N];
ull hh[N];
char s1[N];
char s2[N];
void gethash1() {
    int len = strlen(s1 + 1);
    p[0] = 1;
    for (int i = 1; i <= len; i++) {
        h[i] = h[i - 1] * P + (s1[i] - 'A' + 1);
        p[i] = p[i - 1] * P;
    }
}
void gethash2() {
    int len = strlen(s2 + 1);
    for (int i = 1; i <= len; i++) {
        hh[i] = hh[i - 1] * P + (s2[i] - 'A' + 1);
    }
}
ull get1(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}
ull get2(int l, int r) {
    return hh[r] - hh[l - 1] * p[r - l + 1];
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s%s", s2 + 1, s1 + 1);
        gethash1();
        gethash2();
        int len2 = strlen(s2 + 1), len1 = strlen(s1 + 1);
        ull tmp = get2(1, len2);
        int ans = 0;
        for (int i = 1; i + len2 - 1 <= len1; i++) {
            if (s1[i] != s2[1])
                continue;
            if (get1(i, i + len2 - 1) == tmp)
                ans++;
        }
        cout << ans << endl;
    }
}

06 子串位置

解法

  • 同05题。输出方式略有不同。注意循环的终止条件。
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int P = 131;
typedef unsigned long long ull;
ull h[N], p[N], hh[N];
char a[N], b[N];
int len1, len2;
void gethash() {
    p[0] = 1;
    for (int i = 1; i <= len1; i++) {
        h[i] = h[i - 1] * P + (a[i] - 'A' + 1);
        p[i] = p[i - 1] * P;
    }
    for (int i = 1; i <= len2; i++) {
        hh[i] = hh[i - 1] * P + (b[i] - 'A' + 1);
    }
}
ull get1(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}
ull get2(int l, int r) {
    return hh[r] - hh[l - 1] * p[r - l + 1];
}
int main() {
    scanf("%s%s", a + 1, b + 1);
    len1 = strlen(a + 1);
    len2 = strlen(b + 1);
    gethash();
    ull tmp = get2(1, len2);
    for (int i = 1; i + len2 - 1 <= len1; i++) {
        if (a[i] != b[1])
            continue;
        if (get1(i, i + len2 - 1) == tmp) {
            cout << i << " ";
        }
    }
}