【模板：字符串哈希】LOJ #103. 子串查找

君义_noip

774人浏览 · 2026-01-12 23:18:34

君义_noip · 2026-01-12 23:18:34 发布

【题目链接】

LOJ #103. 子串查找

【题目考点】

1. 字符串哈希

哈希相关概念见：【模板：哈希表】信息学奥赛一本通 1456：【例题2】图书管理
使用基数转换法求一个字符串的哈希值：
给出一个固定进制 $b$ ，将一个字符串上的每个字符看做一个进制位上的数字，所以这个字符串就可以看做一个 $b$ 进制的数，可以配合除留余数法，将这个数的数值再对一个模数取模，就可以得到这个字符串的哈希值。
选取两个互质的常数进制 $b$ 和模数 $M$ $（ b < M ）$ ，假设有字符串 $s$ ，长度为 $n$ ， $c_i$ 是字符 $s_i$ 对应的数字，那么我们定义哈希函数：
$(c_0b^{n-1} + c_1b^{n-2} + ... + c_{n-1}b^0)\bmod M$
注意：

新的基数 $b$ 一般大于字符串 $s$ 对应的数字串的基数。
基数 $b$ 与模数 $M$ 互质， $b$ 一般选择质数。
字符转为对应的数字选择：一般不转为数字 $0$ 。

如果转为数字0，会增加哈希冲突。
假设基数 $b = 10, m = 101$
如果 $c_i = s_i-A$ ，那么’A’对应0， 'B’对应1
$\bmod 101 = 1$
$\bmod 101 = 1$ ，发生了哈希冲突。
如果 $c_i = s_i-A+1$ ，那么’A’对应1， 'B’对应2
$\bmod 101 = 12$
$\bmod 101 = 2$

自然溢出
对于C++中的 $X$ 位无符号整型，当计算结果超出了X位二进制数，变量中只保留最低的X位二进制数，这种机制为自然溢出，其效果相当于对数值取模 $2^X$ 。
可以使用32位无符号整数(unsigned)计算哈希值，并取 $M = 2^{32}$ 。
或使用64位无符号整数(unsigned long long)计算哈希值，并取 $M = 2^{64}$ 。
利用自然溢出省去求模运算。

2. 双哈希

使用再散列法降低哈希冲突。
双哈希：选择不同的基数 $b$ 和模数 $M$ ，用不同的方法对字符串求哈希值。

如果两字符串在两种哈希方法下的哈希值都一样，则可以判定两字符串相同。
如果两字符串在两种哈希方法下得到的哈希值存在不一样的情况，则判断两字符串不同。

2. KMP算法

KMP算法概念本题做法见：

【解题思路】

给定两个字符串 $S$ 、 $T$ ，判断 $T$ 是否是 $S$ 的子串。如果 $T$ 是 $S$ 的子串，返回 $T$ 在 $S$ 中的起始位置，或 $T$ 在 $S$ 中出现的次数。
对子串的定位操作通常称为字符串的模式匹配问题，其中等待匹配的S串为主串，用来匹配的T串为模式串。

解决字符串模式匹配问题，有以下多种解法：

非正解：枚举算法

记主串 $S$ 的长度为 $n$ ，模式串 $T$ 的长度为 $m$

枚举 $S$ 中所有长为 $m$ 的子串
判断 $S$ 中长为 $m$ 的子串与模式串 $T$ 是否相同，如果相同则计数加1。
最后输出计数

该算法的时间复杂度为 $O(n\cdot m)$ ，无法通过此题。

解法1：滚动哈希算法

1. 字符串哈希解题算法

枚举子串求哈希值

求出模式串 $T$ 的哈希值 $h t$
枚举主串中每个长为 $m$ 的子串，求出其哈希值 $h$
如果 $h$ 等于 $h t$ ，再判断子串与模式串是否相同，如相同则进行计数。

单独求长为 $m$ 的子串哈希值的时间复杂度为 $O (m)$ 。如果我们可以通过滚动哈希算法，以 $O (1)$ 的时间复杂度求出每个长为 $m$ 的子串的哈希值，那么解决该问题的总体时间复杂度为 $O (n)$ 。

2. python字符串切片表示方法

以下使用python中字符串切片的写法表示字符串的子串：
$s$ 是字符串型变量， $s_i$ 表示 $s$ 的下标 $i$ 位置的字符，下标从0开始数。
$s [x : y]$ $s$ 下标区间 $[x, y)$ 中的字符构成的子串，即 $s_x\sim s_{y-1}$
$s [: y]$ $s$ 下标区间 $[0, y)$ 中的字符构成的子串，即 $s$ 的前 $y$ 个字符构成的子串。
$s [x :]$ $s$ 下标区间 $[x, 0)$ 中的字符构成的子串，即 $s$ 从 $s_x$ 到末尾字符构成的子串。
$s [x : x + n]$ $s$ 下标区间 $[x, x + n)$ 中的字符构成的子串，即从 $s_x$ 开始长为 $n$ 的子串。

3. 滚动哈希算法

为了可以以 $O (1)$ 时间复杂度求出 $S$ 的每个长为 $m$ 子串的哈希值，我们需要做一些预处理操作。
根据使用基数转换法进行字符串哈希的方法：
选取两个互质的常数进制 $b$ 和模数 $M$ $（ b < M ）$ ，假设有字符串 $s$ ，长度为 $n$ ， $c_i$ 是字符 $s_i$ 对应的数字，那么我们定义哈希函数：
$(c_0b^{n-1} + ... + c_{n-1}b^0)\bmod M$
在本题中 $b$ 取 $31$ ，大于字符串中字符的转成的数值（A~Z转为0~25）。 $M$ 取 $2^{32}$ ，进行自然溢出。
（为了表示方便，以下公式中不再写出 $\bmod\ M$ ，实际是要进行取模的。）
根据上式，可知：
$H(s[:k]) = c_0b^{k-1}+c_1b^{k-2}+ ... +c_{k-1}b^0$
$H(s[:k-1]) = c_0b^{k-2}+c_1b^{k-3}+ ... +c_{k-2}b^0$
$bH(s[:k-1]) = c_0b^{k-1}+c_1b^{k-2}+ ... +c_{k-2}b^1$
$bH(s[:k-1]) +1= c_0b^{k-1}+ ... +c_{k-2}b^1+b^0$
因此： $H (s [: k]) = b H (s [: k - 1]) + 1$
可以先预处理出 $k\in[1, n]$

对于字符串 $s$ 从下标 $k$ 开始长为 $n$ 的子串为 $s [k : k + n]$
$H(s[k:k+n]) = c_kb^{n-1}+c_{k+1}b^{n-2}+... +c_{k+n-1}b^0$
$H(s[:k+n]) =c_0b^{k+n-1}+...+c_{k+n-1}b^0$
已知： $H(s[:k]) = c_0b^{k-1}+ ... +c_{k-1}b^0$
所以： $b^nH(s[:k])=c_0b^{n+k-1}+...+c_{k-1}b^n$
$b^nH(s[:k])+H(s[k:k+n])$
$c_0b^{n+k-1}+...+c_{k-1}b^n+c_kb^{n-1}+... +c_{k+n-1}b^0$
$= H (s [: k + n])$
所以：
$H(s[k:k+n])=H(s[:k+n])-b^nH(s[:k])$
根据此公式，可以在预处理出 $H (s [: i])$ 与 $b^i$ 后，以 $O (1)$ 时间复杂度求出 $s$ 字符串的任意子串的哈希值。

4. 具体实现

将初始化哈希值数组以及求哈希值的过程包装在类Hash中，类内逻辑固定，与外部问题无关。
如何设定模数 $M$ 与基数 $b$ ？，为了减少哈希冲突，二者都要设为质数，基数 $b$ 一般要大于字符串中字符的数值127，模数设大一些可以减少哈希冲突。在以上原则下，两变量的值可以任意设定。

设属性： $b = 131$ ，设bp数组，bp[i]表示 $b^i$ ，设h数组，h[i]表示字符串 $s$ 的前 $i$ 个字符的哈希值，即 $H (s [: i])$ 。
关于模数 $M$ ，可以设置模数，而后计算的过程中进行手动取模（包括进行数学取模）。而且h、bp数组要设为有符号整型，避免结果为负数时发生数值错误。
或者可以将h、bp数组设为无符号整型，进行自然溢出，等价于对 $2^{32}$ (unsigned)，或 $2^{64}$ (unsinged long long)进行取模。
在构造函数中递推求出bp数组的值。同时根据递推式 $+1)\bmod M$ ，求出 $h$ 数组的值。
设getHash(k, n)函数，求 $H (s [k : k + n])$ ，使用公式： $H(s[k:k+n])=(H(s[:k+n])-b^nH(s[:k]))\bmod M$ ，可以求出该子串的哈希值。如果设置了模数 $M$ ，注意要使用数学取模。

主函数中：
对主串 $S$ 和模式串 $T$ 构造Hash类对象。求出主串 $S$ 的长度 $n$ 和模式串 $T$ 的长度 $m$ 。
枚举主串 $S$ 的每个长为 $m$ 的子串，对于子串 $s [i : i + m]$ ，通过调用Hash对象的成员函数getHash判断该子串的哈希值 $H (s [i : i + m]$ 与模式串的哈希值 $H (t [0 : m])$ 是否相同。
如果二者相同，则认为主串 $S$ 中出现了一次 $T$ ，计数器cnt增加1。最后输出子串的数量cnt。

子串 $s [i : i + m]$ 与模式串 $T$ 的哈希值相同，此时理论上应该再判断两字符串各字符是否完全相同。但如果再判断两字符串是否完全相同，本题就会时间超限。
只要哈希的方法合理，两字符串哈希值相同时，大概率二者的字符串是相同的。但如果两字符串不同，但哈希值相同，就发生了哈希冲突，这种情况也是可能存在的。为了减少哈希冲突，我们可以让哈希值的范围更大（如设为unsigned long long类型），或使用双哈希方法，降低哈希冲突发生的概率。
但只要是哈希算法，总是有概率发生哈希冲突的。我们只是人为忽略了这样的小概率事件发生的情况，去赌该题的的测试数据不会让我的哈希算法发生哈希冲突。

解法2：双哈希算法

双哈希概念见【题目考点】中的 3. 双哈希
上述哈希过程中用到了：
b：基数。
M：模数
h数组，h[i]表示 $s [: i]$ 的哈希值
bp数组，bp[i]表示 $b^i$
设DoubleHash类，其中设两套哈希相关的属性
第一套：模数m1=10007，基数b1=131，有h1数组对应h数组，bp1数组对应bp数组。
第二套：模数m2=10009，基数b2=137，有h2数组对应h数组，bp2数组对应bp数组。
构造函数中，对于传入的字符串，同时初始化bp1, bp2, h1, h2数组。
getHash(k, n)函数中，需要求出 $s [k : k + n]$ 在两套哈希方法下的哈希值，将两个哈希值构成一个pair<int, int>类型数对返回。
在比较哈希值时，可以直接使用pair<int, int>类型已经重载的==运算判断两个字符串的双哈希值是否对应相同。
主函数逻辑不变。

【题解代码】

解法1：单哈希+自然溢出

#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
struct Hash
{
	int b = 131; 	
	unsigned h[N], bp[N];//h[i]:s[:i]的哈希值， bp[i]：b^i%M
	Hash(string s)
	{
		bp[0] = 1;
		h[0] = 0;
		for(int i = 1; i <= s.length(); ++i)
		{
			bp[i] = bp[i-1]*b;
			h[i] = (h[i-1]*b+s[i-1]);
		}
	}
	int getHash(int k, int n)//s[k:k+n]的哈希值 
	{
		return h[k+n]-h[k]*bp[n];
	}
}; 
int main()
{
	string s, t;
	cin >> s >> t;
	int cnt = 0, n = s.length(), m = t.length();//n：主串长度 m：模式串长度 
	Hash hs(s), ht(t);
	for(int i = 0; i <= n-m; ++i)
		if(hs.getHash(i, m) == ht.getHash(0, m))//s[i]~s[i+m-1]与t的两种哈希值都相同 
			cnt++;//注意这里理论上应该再做一遍字符串比较，比较s[i]~s[i+m-1]与t是否相同。因为哈希值相同不代表字符串相同。但如果做比较的话，就超时了。 
	cout << cnt << '\n'; 
    return 0;
}

解法2：单哈希+自定义模数

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define MOD(a, b) (((a)%(b)+(b))%(b))
const int N = 1000005;
struct Hash
{
	int b = 131, M = 1e9+7; 	
	LL h[N], bp[N];//h[i]:s[:i]的哈希值， bp[i]：b^i%M
	Hash(string s)
	{
		bp[0] = 1;
		h[0] = 0;
		for(int i = 1; i <= s.length(); ++i)
		{
			bp[i] = bp[i-1]*b%M;
			h[i] = (h[i-1]*b+s[i-1])%M;
		}
	}
	int getHash(int k, int n)//s[k:k+n]的哈希值 
	{
		return MOD(h[k+n]-h[k]*bp[n], M);
	}
}; 
int main()
{
	string s, t;
	cin >> s >> t;
	int cnt = 0, n = s.length(), m = t.length();//n：主串长度 m：模式串长度 
	Hash hs(s), ht(t);
	for(int i = 0; i <= n-m; ++i)
		if(hs.getHash(i, m) == ht.getHash(0, m))//s[i]~s[i+m-1]与t的两种哈希值都相同 
			cnt++;//注意这里理论上应该再做一遍字符串比较，比较s[i]~s[i+m-1]与t是否相同。因为哈希值相同不代表字符串相同。但如果做比较的话，就超时了。 
	cout << cnt << '\n'; 
    return 0;
}

解法3：双哈希

#include <bits/stdc++.h>
using namespace std;
#define MOD(a, b) (((a)%(b)+(b))%(b))
const int N = 1000005;
struct DoubleHash
{
	int b1 = 131, b2 = 137, m1 = 10007, m2 = 10009; 	
	int h1[N], h2[N], bp1[N], bp2[N];//h1[i]:第1种哈希方法下s[0]~s[i-1]的哈希值， bp1[i]：b1^i%m1 h2[i]:第2种哈希方法下s[0]~s[i-1]的哈希值， bp2[i]：b2^i%m2 
	DoubleHash(string s)
	{
		bp1[0] = bp2[0] = 1;
		h1[0] = h2[0] = 0;
		for(int i = 1; i <= s.length(); ++i)
		{
			bp1[i] = bp1[i-1]*b1%m1;
			bp2[i] = bp2[i-1]*b2%m2;
			h1[i] = (h1[i-1]*b1+s[i-1])%m1;
			h2[i] = (h2[i-1]*b2+s[i-1])%m2;
		}
	}
	pair<int, int> getHash(int k, int n)//取s从k开始长为n的子串的双哈希值 
	{
		return {MOD(h1[k+n]-h1[k]*bp1[n], m1), MOD(h2[k+n]-h2[k]*bp2[n], m2)};
	}
}; 
int main()
{
	string s, t;
	cin >> s >> t;
	int cnt = 0, n = s.length(), m = t.length();//n：主串长度 m：模式串长度 
	DoubleHash hs(s), ht(t);
	for(int i = 0; i <= n-m; ++i)
		if(hs.getHash(i, m) == ht.getHash(0, m))//s[i]~s[i+m-1]与t的两种哈希值都相同 
			cnt++;//注意这里理论上应该再做一遍字符串比较，比较s[i]~s[i+m-1]与t是否相同。因为哈希值相同不代表字符串相同。但如果做比较的话，就超时了。 
	cout << cnt << '\n'; 
    return 0;
}