「题单题解」字符串 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