「题单题解」字符串 Hash
Coffee_zzz
·
2024-12-30 20:33:45
·
算法·理论
题单链接：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_j 与 s_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 ，并把 s 与 t[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 的限制，我们可以知道，只有 k 个 0 和 k 个 1 交替出现的字符串才是 k -proper 的；一共只有两种 k -proper 的字符串，我们设其分别为 x 和 y 。
我们设 t 为翻转 s 所得到的字符串，即 t=s^R 。
设对位置 p 进行操作后的字符串为 r ，则根据操作规则可知 r=s[p+1,n]+t[n-p+1,n] ；我们只需要判断是否满足 r=x 或 r=y ，这显然可以用 Hash 函数计算。
预处理后枚举每个位置即可。时间复杂度 \mathcal O(n) 。
参考代码：https://www.luogu.com/paste/xhks0wp6
P8023 [ONTAK2015] Tasowanie
由于题目要求 T 的字典序最小，容易想到最朴素的贪心：同时从前往后枚举 A 和 B 的每个元素，设当前枚举到了 A_i 和 B_j ：
若 A_i \lt B_j ，则把 A_i 加入到 T 的末尾，并把 i 增加 1 ；
若 A_i \gt B_j ，则把 B_j 加入到 T 的末尾，并把 j 增加 1 。
但是当 A_i = B_j 的时候，选择 A_i 或 B_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 更优。我们可以通过在 A 和 B 的末尾添加一个极大值的方式来更方便地处理。
时间复杂度 \mathcal O(n \log n) 。
参考代码：https://www.luogu.com/paste/71alnyun
P3763 [TJOI2017] DNA
为了方便，我们设给定的两个字符串分别为 s 和 t ，长度分别为 n 和 m 。
我们考虑枚举 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 的正整数 j ，S[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 放到一起处理。
考虑完 T 和 C 后，我们来考虑 A 和 B 。我们把 T 拆成 A 和 B ，那我们现在要解决的问题是，求出存在多少种拆分方案，满足 F(A) \le F(C) 。
对于每个不大于 n 的正整数 i ，我们预处理出 c_i 和 d_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 的正整数 k ，f_k 的值即为 i 。其中我们可以认为 c_{n+1}=0 ，c_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