当前位置：首页 > news >正文

笔记哈希

news 2025/9/13 23:49:40

A - Description

给定字符串 $S$ 和 $T$，问你在 $S$ 中 $T$ 出现了几次。

$1\le |S|,|T|\le 2\times 10^6$

A - Solution

首先暴力地来想。在 $S$ 中找出所有长度为 $|T|$ 的子串，然后暴力逐字符匹配，复杂度显然是 $O(n^2)$ 的，考虑优化。（此处假设 $|T|$ 与 $|S|$ 同阶，记为 $n$ ）

枚举所有子串的过程较难优化，我们考虑优化逐字符匹配的过程。逐字符匹配本质上就是比较两个字符串是否相等，那我们能否将这个过程优化成 $O(1)$ 呢？

于是，字符串哈希应运而生。我们可以使用字符串哈希将字符串压成一个数，然后就可以 $O(1)$ 比较了。考虑将这个字符串转化为一个 $k$ 进制数，也就是给第 $i$ 位乘上 $k^{i-1}$ 的权值。防止大数溢出，可以设定模数进行取模（不过大多数时候 unsigned long long 是不错的选择）

时间复杂度 $O(n)$，瓶颈在于枚举长度为 $|T|$ 的子串。

B - Description

给定字符串 $S$，有 $q$ 次询问，每次询问给出 $x$ 和 $y$，让你求字符串 $s_1=S_xS_{x+1}\cdots S_{n}$ 和 $s_2=S_yS_{y+1}\cdots S_n$ 的最长公共前缀长度。

B - Solution

还是暴力地来想。假设答案为 $len$，那么就有 $S_xS_{x+1}\cdots S_{x+len-1}=S_yS_{y+1}S_{y+len-1}$ ，有了前面的哈希支持，我们可以做到 $O(1)$ 判断这个式子。我们现在可以枚举从 $1$ 到 $n-\max(x,y)+1$ 的每个 $len$（记 $n=|S|$，下文如没有特殊说明均代表此含义），时间复杂度是 $O(qn)$ 的。

进行一些观察，我们发现 $len$ 是具有单调性的。具体来说，如果 $len=5$ 时满足条件，那么 $n=4$ 时一定满足，因为这是被 $len=5$ 完全包含的。如果令 $a_i$ 代表 $len=i$ 时是否符合条件，那么 $01$ 数组 $a$ 的形式一定是 $1111\cdots 10000\cdots 0$。

因此，我们考虑二分 $len$。具体地，每二分出一个 $mid$，我们使用哈希 $O(1)$ 判断是否符合条件，如果符合就去二分 $>mid$ 的值，如果不符合就二分 $<mid$ 的值。时间复杂度为 $O(q\log n)$，可以通过。

C - Description

给你一个由小写英文字母构成的字符串 $S$，求 $S$ 中最长回文串的长度。

$1\le n\le 10^6$。

C - Solution

我们先从回文串的定义角度入手。通俗一点来说，回文串就是指从前往后读和从后往前读是相同的。形式化地，对于一个字符串 $s$，有 $s_1s_2\cdots s_n=s_ns_{n-1}\cdots s_1$。不过貌似和最长没有什么关系，所以换一种方法表示。$s_1s_2\cdots s_{mid}=s_{n}s_{n-1}\cdots s_{mid}$。现在我们把答案扩展到了一个 $mid$ 上。$mid$ 是可以从 $1$ 到 $n$ 枚举的，所以现在只需要考虑 $mid$ 为定值时的情况。

对于这种极值问题，我们可以将它转化为判定性问题。具体地，对于每一个 $1\le mid \le n$，我们需要求出最大的 $len$，使得

\[s_{mid-len+1}s_{mid-len+2}\cdots s_{mid}=s_{mid+len-1}s_{mid+len-2}\cdots s_{mid} \]

根据上一道题的观察，$len$ 也是具有单调性，可以二分的。而上面的式子也是可以哈希 $O(1)$ 判断的。因此，我们解决了这个问题。

流程如下：

枚举每个 $1\le mid \le n$，需要 $O(n)$
二分出最大的 $len$，满足上面的等式（哈希判断），需要 $O(\log n)$。

哦哦其实并没有解决这个问题。因为我们还不知道如何求解一个区间内字符的哈希值。

我们先列出来最基本的求区间 $\left [ 1,i\right ]$ 哈希的式子：

\[hash\left [ i\right ]=\sum_{j=1}^i s_j\times base^{i-j} \]

那么如何用已知的 $hash$ 数组表示一个区间 $\left [ l,r\right ]$ 的哈希值？

\[\begin{align} hash(l,r)&=\sum_{j=l}^r s_j\times base^{r-j}\\ &=\sum_{j=1}^rs_j\times base^{r-j}-\sum_{j=1}^{l-1}s_j\times base^{r-j}\\ &=hash\left [r\right ]-hash\left [ l-1 \right ]\times base^{r-j-(l-1-j)}\\ &=hash \left [r\right ]-hash\left [l-1\right ]\times base^{r-l+1} \end{align} \]

写点解析吧。

第一行：将 $l$ 到 $r$ 这个子串表示为 $base$ 进制数。可以理解为把 $l$ 到 $r$ 单独看成一个字符串重新哈希得到的值。

第二行：类似前缀和的操作，显然正确。

第三行：注意到这个式子中减号前后的形式基本与最开始的哈希式子一样，于是改写成 $hash$ 数组。后者在区间哈希的式子中 $base$ 的幂次是 $r-j$，而写成 $hash[l-1]$ 的话幂次就应该是 $l-1-j$。

第四行是简单化简，于是我们得到了 $O(1)$ 区间哈希的方法。

综上，时间复杂度为 $O(n\log n)$。

D - Description

给你一个长度为 $n$ 的序列 $a$，保证对于每个 $1\le i\le n$ 有 $1\le a_i\le n$，有 $q$ 次询问，每次询问给定两个正整数 $l,r$，你需要回答区间 $\left [l,r\right ]$ 是否是 $\left [1,r-l+1\right ]$ 的排列。

$1\le n,q\le 10^6$。

D - Solution

首先，我们发现如果 $\left [ l,r \right ]$ 是 $\left [ 1,r-l+1 \right ]$ 的排列，那么这两个区间和一定相等。因此， $\left [l,r \right ]$ 的区间和一定等于 $\frac{x\times (x+1)}{2}$（$x=r-l+1$，即为区间长度）。只有这一个条件显然是不严谨的，我们再将排列的基本性质放到限制里：区间中的 $x$ 个元素各不相同。

形式化地，满足下面两个条件的区间是符合条件的。