「题单题解」字符串 Hash

· · 算法·理论

题单链接:https://www.luogu.com.cn/training/682394

P3370 【模板】字符串哈希

直接使用字符串 Hash 即可。

本题数据较弱,加强版可以看 U461211 字符串 Hash(数据加强)。

参考代码:https://www.luogu.com/paste/r6ggp5on

P1481 魔族密码

首先把所有字符串按照长度从小到大排序,方便我们后续 dp。

我们定义 dp_i 表示以 s_i 结尾的词链的最大长度,容易得到转移方程:

dp_i=\left(\max\limits_{s_j \in p_i} dp_j\right)+1

其中 p_i 表示所有 s_i 的前缀组成的集合。

转移时,我们只需要枚举所有小于 i 的正整数 j,并用 Hash 函数判断 s_js_i[1,|s_j|] 是否相等即可。

答案即为 \max\limits_{i=1}^n dp_i。时间复杂度 \mathcal O(n^2)

参考代码:https://www.luogu.com/paste/wp6hdq17

CF1200E Compress Words

对于每次合并,设左侧的字符串为 s,长度为 n,右侧的字符串为 t,长度为 m

len=\min(n,m),我们可以处理出 s 的长度不大于 len 的后缀的 Hash 函数值和 t 的长度不大于 len 的前缀的 Hash 函数值,找到最大的满足 s[n-i+1,n]=t[1,i] 的非负整数 i,并把 st[i+1,m] 合并。每次合并的时间复杂度为 \mathcal O(len)

由于 len \le m,所以总的时间复杂度为 \mathcal O(siz),其中 siz 表示所有字符串的长度之和。

参考代码:https://www.luogu.com/paste/6uzacmrr

CF1979D Fixing a Binary String

根据 k-proper 的限制,我们可以知道,只有 k0k1 交替出现的字符串才是 k-proper 的;一共只有两种 k-proper 的字符串,我们设其分别为 xy

我们设 t 为翻转 s 所得到的字符串,即 t=s^R

设对位置 p 进行操作后的字符串为 r,则根据操作规则可知 r=s[p+1,n]+t[n-p+1,n];我们只需要判断是否满足 r=xr=y,这显然可以用 Hash 函数计算。

预处理后枚举每个位置即可。时间复杂度 \mathcal O(n)

参考代码:https://www.luogu.com/paste/xhks0wp6

P8023 [ONTAK2015] Tasowanie

由于题目要求 T 的字典序最小,容易想到最朴素的贪心:同时从前往后枚举 AB 的每个元素,设当前枚举到了 A_iB_j

但是当 A_i = B_j 的时候,选择 A_iB_j 可能会有不同的影响。这时,我们可以继续考虑贪心。

我们可以通过二分和 Hash 函数,找到最大的非负整数 l,使得 A[i,i+l-1]=B[j,j+l-1],然后比较 A_{i+l}B_{j+l}
如果 A_{i+l} \lt B_{j+l},则选择 A_i 一定更优,否则选择 B_j 一定更优。注意,如果 i+l=n+1,则选择 B_j 更优;同理,如果 j+l=m+1,则选择 A_i 更优。我们可以通过在 AB 的末尾添加一个极大值的方式来更方便地处理。

时间复杂度 \mathcal O(n \log n)

参考代码:https://www.luogu.com/paste/71alnyun

P3763 [TJOI2017] DNA

为了方便,我们设给定的两个字符串分别为 st,长度分别为 nm

我们考虑枚举 s 中每个长度为 m 的子串 s[i,i+m-1],判断其是否可以通过不大于 3 次修改变成字符串 t

我们可以通过二分和 Hash 函数不断找到最靠左的失配位置,把其与其左侧的部分删除并继续尝试匹配。若在不大于 3 次删除后匹配成功了,则代表该子串可以通过不大于 3 次修改变成字符串 t

每次匹配的时间复杂度是 \mathcal O(\log m) 的,总时间复杂度为 \mathcal O(Tn \log m)

参考代码:https://www.luogu.com/paste/9ud65ody

P7114 [NOIP2020] 字符串匹配

n=|S|

我们首先把一个 A 和一个 B 看成一个整体 T,考虑求出将 S 分为 T^kC 的方案数。

我们可以枚举 T 的长度 i,则 T=S[1,i]。接着,我们继续枚举,通过 Hash 函数,求出最大的满足 S[1,ik]=T^k 的正整数 k
由于 1 \le k \le \dfrac n i,所以直接枚举的复杂度是调和级数的,即 \mathcal O(n \log n)

此时,对于任意不大于 k 的正整数 jS[ij+1,n] 都可以作为 C 的内容。

注意到,当 j \ge 3 时,因为 S[i(j-1)+1,ij]=S[i(j-2)+1,i(j-1)]=T,所以 S[i(j-2)+1,ij] 中的每个字符的出现次数均为偶数;这导致,当 j 的奇偶性相同时,F(C) 的值一定相同。
于是,我们可以考虑把所有奇偶性相同的 j 放到一起处理。

考虑完 TC 后,我们来考虑 AB。我们把 T 拆成 AB,那我们现在要解决的问题是,求出存在多少种拆分方案,满足 F(A) \le F(C)

对于每个不大于 n 的正整数 i,我们预处理出 c_id_i,其中 c_i 表示在 S[1,i] 中出现奇数次的字符的数量,d_i 表示在 S[i,n] 中出现奇数次的字符的数量。
同时,对于每个不大于 n 的正整数 i 和每个小于 26 的非负整数 j,我们预处理出 sum_{i,j},表示满足 c_x \le j 的不大于 i 的正整数 x 的数量。

于是,F(A) 的值就可以被表示为 c_{|A|}F(C) 的值就可以被表示为 d_{ij+1}

j 的奇偶性与 k 相同时,F(C)=d_{ik+1},满足条件的拆分方案数量为 sum_{i-1,d_{ik+1}}。由于共有 \left\lceil\dfrac k 2\right\rceil 个与 k 奇偶性相同的正整数 j,所以这种情况对答案的贡献为:

sum_{i-1,d_{ik+1}} \times \left\lceil\dfrac k 2\right\rceil

j 的奇偶性与 k 不同时,F(C)=d_{i(k-1)+1},满足条件的拆分方案数量为 sum_{i-1,d_{i(k-1)+1}}。由于共有 \left\lfloor\dfrac k 2\right\rfloor 个与 k 奇偶性不同的正整数 j,所以这种情况对答案的贡献为:

sum_{i-1,d_{i(k-1)+1}} \times \left\lfloor\dfrac k 2\right\rfloor

直接对于所有大于 1 且小于 n 的正整数 i 分别计算贡献并求和即可。

本题时限较紧,较为卡常,字符串 Hash 部分可以使用自然溢出。

时间复杂度 \mathcal O(Tn \log n+TnV),其中 V=26

参考代码:https://www.luogu.com/paste/776zex5u

CF1968G1 Division + LCP (easy version)

注意到问题可以转化为,找到最大的非负整数 i,使得 s 中存在至少 l 个不相交的等于 s[1,i] 的子串。

显然,如果 s 中存在至少 l 个不相交的等于 s[1,i+1] 的子串,那么 s 中必然存在至少 l 个不相交的等于 s[1,i] 的子串。答案存在单调性,于是我们可以尝试通过二分找到最大的满足条件的非负整数 i

判断是否存在至少 l 个不相交的等于 s[1,i] 的子串是简单的,只需要从左往右枚举每个长度为 i 的子串,通过字符串 Hash 判断是否和 s[1,i] 相等即可。
注意这些子串不能相交,所以如果 s[k,k+i-1] 匹配成功了,下一次需要从 k+i 开始枚举。

直接二分 i 即可。时间复杂度 \mathcal O(n \log n)

参考代码:https://www.luogu.com/paste/rmfdvr8z

CF1968G2 Division + LCP (hard version)

我们考虑直接枚举每个长度 i,求出 s 所包含的不相交的等于 s[1,i] 的子串的数量 c_i

那么显然,对于所有满足 c_{i+1} \lt k \le c_i 的正整数 kf_k 的值即为 i。其中我们可以认为 c_{n+1}=0c_0=n

于是我们现在只需要思考如何快速求出 c 数组。

如果使用 easy version 的方法,暴力枚举每个长度为 i 的子串,总复杂度是 \mathcal O(n^2) 的,无法接受,考虑优化。

注意到,如果某个子串匹配成功了,下标会直接增加 i。如果每次都匹配成功,总复杂度是调和级数的,即 \mathcal O(n \log n)

我们可以利用二分和 Hash 函数,求出对于每个位置 k,最大的满足 s[1,p_k]=s[k,k+p_k-1] 的非负整数 p_k

我们从大到小枚举长度 i,每次把所有满足 p_k=i 的正整数 k 进行标记后再求 c_i 的值。
在寻找可以被匹配的子串时,我们不需要一位一位枚举,只需要找到在不小于当前下标的正整数中,最小的被标记的正整数即可。其中,最小的被标记的正整数显然可以用线段树维护。

时间复杂度 \mathcal O(n \log^2 n)

参考代码:https://www.luogu.com/paste/xa04h54q