字符串哈希

文章目录

理论基础
字符串前缀哈希
- 哈希函数及公式
- 区间哈希
- 代码实现(C++)
算法应用
- 判断子串是否相等
- - 例题
  - - 输入格式
    - 输出格式
    - 数据范围
    - 输入样例：
    - 输出样例：
- 判断子串是否是回文
- - 例题 **google kickstart Round E P3**
  - - 输入格式
    - 输出格式
    - 数据范围
    - 输入样例：
    - 输出样例：
    - 样例解释
参考

理论基础

字符串哈希，即把一个字符串映射为一个整数，这个整数称之为hash code。在理想状态下，只有两个字符串完全相等， hash code才会相等。因此可以用两个字符串的hash code来判断字符串是否相等。

将字符串转化为整数的函数也叫做哈希函数。

字符串前缀哈希

字符串前缀哈希是前缀思想在哈希中的应用，一般用来解决多次查询子串哈希的问题。

单次计算一个字符串的哈希值复杂度是 O(n)，其中n为串长，与暴力匹配没有区别，如果需要多次询问一个字符串的子串的哈希值，每次重新计算效率非常低下。

因此可以使用特别的哈希函数，使用字符串前缀的哈希值而推出任一连续子串的哈希值。

哈希函数及公式

设字符串S， S中元素下标从1开始， S下标为i的元素为S[i].

哈希函数：
$\sum_{i = 1}^nS[i] * p^{n - i}$
如字符串"abc"，表达式为
$a * p ^ 2 + b * p + c$
利用此公式，我们可以求出S的所有前缀的哈希值

但显然不可能对所有前缀都应用上述公式。事实上pref[i] 可以由pref[i-1]递推得到

仍然以"abc"举例
${ pref[1] = a\ pref[2] = a * p + b\ pref[3] = a * p ^ 2 + b * p + c }$
可以发现

pref[i] = pref[i-1] * p + S[i]

区间哈希

我们得到了一个字符串所有长度前缀的哈希值，那么如何利用它来得到某个区间[l, r]的哈希值呢？

以"abc"举例
${ pref[1] = a\ pref[2] = a * p + b\ pref[3] = a * p ^ 2 + b * p + c }$
假设我们要求[2, 3]区间，即"bc"的哈希，按上述哈希函数应该是b*p + c

类比前缀和sum[l, r] = pref[r] - pref[l-1], 可以发现
$b * p + c = pref[3] - pref[1] * p ^ 2$
事实上，存在以下通式
$hashCode[l, r] = pref[r] - pref[l - 1] * p^{r - l + 1}$
证明并不难，若有兴趣自行研究，就不在此赘述了。

其中r - l + 1很明显的，可以记忆为区间的长度。

因此通过预处理字符串所有前缀的哈希，我们可以以O(1)的时间代价求出任一子串的哈希值。

代码实现(C++)

#define ull unsigned long long 
string s;//源字符串， 下标从1开始
int n; //字符串长度
const ull P = 131;
ull hh[N]; // hh[i] 表示长度为i的前缀子串的哈希
ull p[N];// p[i]表示P的i次幂, 避免使用幂函数多次求幂

// 初始化前缀哈希
void InitHash() {
    p[0] = 1;
    for(int i=1; i<=n; i++) {
        hh[i] = hh[i-1] * P + s[i];
        p[i] = p[i-1] * P;
    }
}

// 获取区间哈希
ull get(int l, int r) {
    return hh[r] - hh[l - 1] * p[r - l + 1];
}

小科普： unsigned long long

ull(unsigned long long)表示64位无符号正整数，之所以使用ull是因为ull溢出后，不会像有符号整数如int那样变成负数，而是会从0重新开始，即等同于对 $2 ^ {64}$ 自动取余。

在上述哈希函数中， P选取为131(此质数在先人的实验中表现最好，不容易发生冲突)，而hashCode更是以幂级增长的，因此很容易就溢出，需要对其进行取模。

算法应用

判断子串是否相等

要判断两个子串是否相等，只需比较哈希值是否相等即可。预处理前缀哈希，即可以O(1)的时间代价得到子串的哈希。

例题

AcWing 841

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1, r1, l2, r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 n 和 m，表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

接下来 m 行，每行包含四个整数 l1, r1, l2, r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从 1 开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤ $10^5$

输入样例：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例：
Yes
No
Yes

套上上面的板子即可

时间复杂度：O(n)

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long

const int N = 1e5 + 10;
const ull P = 131;
ull hh[N], p[N];
string s;
int n;

void InitHash() {
    p[0] = 1;
    for(int i=1; i<=n; i++) {
        hh[i] = hh[i-1] * P + s[i];
        p[i] = p[i-1] * P;
    }
}

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

int main() {
    int m;
    cin >> n >> m >> s;
    s.insert(0, "0");
    InitHash();
    while(m --) {
        int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;
        cout << (get(l1, r1) == get(l2, r2) ? "Yes" : "No") << endl;
    }
}

判断子串是否是回文

回文即源串与反转后的字符串是相同的。

用字符串哈希的角度来解决就是判断一个字符串及其逆转后的字符串哈希值是否相等。

因此我们可以预处理主串的正向哈希以及逆向哈希，再判断某子串的正向哈希和逆向哈希是否相等来判断是否是回文。

#define ull unsigned long long 
string s;//源字符串， 下标从1开始
int n; //字符串长度
const ull P = 131;
ull hh[N], r_hh[N];//前缀、后缀哈希
ull p[N];

// 初始化前缀/后缀哈希
void InitHash() {
    p[0] = 1;
    for(int i=1; i<=n; i++) {
        hh[i] = hh[i-1] * P + s[i];
        r_hh[i] = r_hh[i-1] * P + s[n - i + 1];
        p[i] = p[i-1] * P;
    }
}

// 获取区间哈希
ull get(int l, int r) {
    return hh[r] - hh[l - 1] * p[r - l + 1];
}

ull get_r(int l, int r) {
    return r_hh[n - l + 1] - r_hh[n - r] * p[r - l + 1];
}

bool is_palindrome(int l, int r) {
    return get(l ,r) == get_r(l, r);
}

例题 google kickstart Round E P3

给定一个长度为 N 的回文字符串 P，它仅由小写英文字母构成。

请你找到最短的非空回文字符串 Q，使得 P 与 Q 拼接而成的字符串 Q 也是一个回文串。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含一个整数 N。

第二行包含一个长度为 N 的回文字符串 PP。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 xx 为组别编号（从 11 开始），y 为满足条件的最短非空回文字符串 Q。

数据范围

1≤T≤100
1≤N≤10⁵，
保证 P 是一个由小写字母构成的回文字符串。

输入样例：
3
4
abba
4
cccc
6
cdccdc
输出样例：
Case #1: abba
Case #2: c
Case #3: cdc
样例解释

在 Case 1 中，满足条件的最短回文串 Q 为 abba，此时串联字符串 Q 为 abbaabba，这是一个回文串。

在 Case 2 中，满足条件的最短回文串 Q 为 c，此时串联字符串 PQ为 ccccc，这是一个回文串。

在 Case 3 中，满足条件的最短回文串 Q 为 cdc，此时串联字符串 PQ 为 cdccdccdc，这是一个回文串。

题意分析

给定回文字符串P, 求一回文字符串Q，使在P末尾拼接Q后， PQ仍为回文字符串。

不难分析得到，由于PQ是回文字符串，则P中长度等于Q的前缀应该与Q成倒序关系，设这个前缀为P1, P中除去P1的后半部分为P2。又因为Q为回文字符串，所以P1会等于Q， P1为回文字符串。而P2显然也要是回文字符串，这样才能满足PQ为回文字符串。

因此，将问题剥析出来就是：求最小的整数mid（1~n）, 使得P[1, mid]和P[mid+1, n]均为回文字符串。

参考代码，时间复杂度：O(n)

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long 
string s;
int n; 
const ull P = 131;
const int N = 1e5 + 10;
ull hh[N], r_hh[N];
ull p[N];

void InitHash() {
    p[0] = 1;
    for(int i=1; i<=n; i++) {
        hh[i] = hh[i-1] * P + s[i];
        r_hh[i] = r_hh[i-1] * P + s[n - i + 1];
        p[i] = p[i-1] * P;
    }
}
//获取正哈希
ull get(int l, int r) {
    return hh[r] - hh[l - 1] * p[r - l + 1];
}

//获取反哈希
ull get_r(int l, int r) {
    return r_hh[n - l + 1] - r_hh[n - r] * p[r - l + 1];
}

//判断回文
bool is_palindrome(int l, int r) {
    return get(l ,r) == get_r(l, r);
}

int main() {
    int T; cin >> T;
    for(int t=1; t<=T; t++) {
        cout << "Case #" << t << ": "; 
        cin >> n >> s;
        s.insert(0, "0");//调整下标
        InitHash();
        for(int i=1; i<=n; i++) {//枚举mid
            if(is_palindrome(1, i) && is_palindrome(i+1, n)) {
                cout << s.substr(1, i) << endl;
                break;
            }
        }
    }
}

参考

字符串哈希 - OI Wiki ()

【算法学习笔记】7：字符串前缀哈希法_LauZyHou的博客-****博客

AcWing 841. 字符串哈希 - AcWing

文章目录

理论基础

字符串前缀哈希

哈希函数及公式

区间哈希

代码实现(C++)

算法应用

判断子串是否相等

例题

输入格式

输出格式

数据范围

输入样例：

输出样例：