5-28 字符串杂题

训练一共布置了 8 题，其中除了 H 以外，剩下的题目都是字符串题。这些题全部都可以只用哈希做，也全部都可以不用哈希做。

CF126B - Password

题意：要求找到一个字符串同时是 $S$ 的前缀、后缀、非前后缀子串。

哈希做法：首先，我们要查找，需要多短的前缀才能保证其有过非前后缀子串的出现。我们发现，符合这一条件的前缀长度是单调的，我们就可以二分答案，然后枚举子串出现的位置（不能是后缀），用哈希 $O(1)$ 判断。然后对于所有符合条件的前缀，哈希判断它是否和等长的后缀相同即可。总复杂度 $O(n\log n)$。

KMP 做法：我们利用 KMP 的 $border$ 长度计算需要多段的前缀保证非前后缀子串出现。如果在 $[1,n-1]$出现了长度为 $s$ 的 $border$，因为其定义是真后缀，所以长度为小于等于 $s$ 的都可以。然后从全串的 $border$ 跳失配前缀，直到当前的前缀长度满足要求。复杂度 $O(n)$。

SAM 做法：用 SAM 的 Parent Tree 上启发式合并维护 $endpos$ 集合，注意我们只需要从 $\{n\}$ 的节点往上跳父亲，因为必须有 $n$ 在。然后判断集合大小是否大于 $2$，$len$ 是否恰好使得最小结束位置为前缀。复杂度是启发式合并的 $O(n\log n)$。

CF631D - Messenger

题意：我们用压缩连续段的方式存储两个字符串，求字符串 $t$ 在 $s$ 中出现的次数。

第一步合并字符相同的连续段，使得每个连续段都是极大的。

如果 $t$ 只有一个连续段，一定是被 $s$ 的某个和它字符相同的连续段完全包含。
如果 $t$ 只有两个连续段，一定是 $s$ 的相邻两个字符相同的连续段的后缀和前缀，枚举即可。
如果 $t$ 有三个或以上连续段，首先，需要第二个到倒数第二个和 $s$ 中的一个子串完全匹配。其次，$s$ 中匹配上的子串左右分别和 $t$ 的第一个和最后一个连续段字符相同。

我们发现，第一种和第二种情况可以直接枚举，对于第三种，我们可以把一个连续段当成一个字符，先求出 $t$ 的中间部分和 $s$ 的所有匹配，然后检查左右是否符合要求。

KMP 本身对于字符集没有什么要求，所以可以直接做。复杂度 $O(n)$。

哈希会稍微麻烦一些，但是我们可以用离散化的方式给每个存在的 $(l,ch)$ 赋上一个互不相同的权值，就可以正常做。瓶颈在离散化，因为 map 的原因是 $O(n\log n)$。

CF25E

题意：给出三个字符串，求最短的将这三个字符串作为子串的字符串长度。

首先，我们把子串处理掉。也就是，如果 $s_i$ 是 $s_j$ 的子串，$s_i$ 就不必出现了。我们可以直接枚举，然后 KMP 或者哈希判断子串。特别注意，如果两个串相同，要保留一个。

然后，剩下的 $1/2/3$ 个串都互不为子串。我们枚举它们在最终串中的排列方式。其中，第一个串和第二个串不相交的部分和最后一个肯定不相交，否则第二个串就是它的子串了。那么我们可以将 $s_1,s_2$ 的贡献和 $s_2,s_3$ 的贡献分开计算。我们发现，因为互不为子串，将 $s$ 和 $t$ 拼起来的最长的重合部分，就是字符串 $t+'$'+s$ 的最长 $border$，可以直接用 KMP 求取，或者用哈希暴力判断。

这样，我们就求出了最长的重合部分，也就求出的最短的总长度。复杂度是 $O((k^2+k!)n)$

CF427D

题意：给出两个字符串，求最短的字符串使得其在两个串中各恰好出现一次。

哈希做法：

平方地暴力枚举子串，把子串的哈希值存进哈希表。然后暴力枚举可行的哈希值，找到两个表中值都是 $1$ 的最短子串。但是这样存在很多问题，首先，哈希表要存 $n^2$ 个值，空间很大。其次，取模哈希过慢，几乎无法通过这题。最后，哈希值数量过多，冲突概率过大。

我们考虑别的优化，第一，用 unsigned int 自然溢出替代取模哈希（注意 Base 要换成奇数）。第二，我们可以从小到大的枚举长度，只在哈希表中存当前长度的所有子串哈希值，对当前长度判断完之后就清空哈希表。这样就同时解决了空间不够和 unsigned int 冲突概率大的问题。

最后，出题人非常阴险的卡掉了很多的常见模数以及自然溢出 $100$ 以内的大多数 Base，我换了 Base=191981 才通过，复杂度 $O(n^2)$ 而且常数很大。

SAM 做法：

把两个字符串中间加上特殊符号连接然后求 SAM，在 SAM 的 Parent Tree 上启发式合并维护 $endpos$ 集合。然后检查当前节点的集合是否恰好大小为 $2$ 且分别落在 $s$ 和 $t$ 中作为答案。复杂度 $O(n\log n)$，但实际上我们发现大于 $2$ 的集合是没用的，所以不需要合并那么多，只需要第一层即可，所以可以优化到 $O(n)$。

Z 做法：

枚举 $s$ 的后缀 $c$，然后将新的字符串设置为 c+$+s+$+t。然后求出 $z$ 函数。忽略 $c$ 原来的位置，我们要的答案是只出现一次的，那么 $(非严格次大值,最大值]$ 之间的任何长度都符合条件。直接枚举就可以了。复杂度 $O(n^2)$，常数略大（因为每次对 $2n$ 求 $z$ 函数）

SA 做法：

先特殊符号拼接然后求 $sa$ 和 $lcp$，然后对于符合要求的串，一定是它们两个分别落在左边和右边，并且 $lcp$ 上连续。同时它只能出现一次，所以必须比相邻的其他 $lcp$ 值要大。其实就是和上一个一样了。比两边都大，比自己小即可。复杂度 $O(n\log n)$。

CF533F - Encoding

哈希做法：枚举子串的位置。首先要判断形态相同。我们对每个字符单独哈希，然后将其排序。哈希值非 $0$ 且相同的字母一定是互相对应的。我们可以在它们之间建立双向关系。如果一个字符要建立关系的对象已经有关系且不是它，这个位置就不满足条件。如果某个数的哈希值甚至找不到对应的解，就直接不满足条件。因为要排序或者 map 查找哈希值，复杂度 $O(n|\Sigma|\log|\Sigma|)$。

KMP 做法：枚举字符 $x$ 替换到字符 $y$，把 $t$ 中所有 $x$ 变成 $1$，其他都是 $0$，对 $s$ 和 $y$ 一样。然后跑 KMP 匹配，在所有匹配上的位置，都要求 $x$ 和 $y$ 互相替换。然后枚举位置，判断当前子串需要匹配上 $t$，哪些字符需要配对，它们之间互相是否冲突。复杂度 $O(n|\Sigma|^2)$，也能过。

[NOIP2020] 字符串匹配

首先，我们预处理每个前缀和后缀中出现奇数次的字符数量。然后我们枚举 $|AB|$，枚举 $i$。由调和级数可证一共枚举了 $O(n\log n)$ 次。然后我们需要计算 $|AB|$ 的 $F(A)\le F(C)$ 的前缀数量。我们可以提前存起来然后用树状数组求解。在枚举 $i$ 的时候需要判断新加入的子串是否和原先的循环节相同。因为是和前缀比较，所以既可以用 Z 函数也可以用哈希。

ARC060D - Best Representation

诈骗题。给了个模数但是答案根本达不到那个级别。

先提前给出一个引理，如果长度为 $2n$ 的 $s$ 有 $s[1,n]=s[n+1,2n]$ 并且 $s[1,m]=s[m+1,2m](m<n)$ 或者 $s[1,2n-m+1]=s[m+1,2n](n<m<2n)$，那么一定存在长度为 $\gcd(2n,m)$ 的循环节。很好证，因为其实就是证明划分单位，$2n,m$ 互质之后 $s$ 的任何位都相等。而每次从第一个到第二个就是 $i$ 和 $i+m$ 相同，而 $\bmod 2n$ 的环下面，一直 $+m$ 走能遍历所有数，也就得证了。

我们考虑当前字符串的最小循环节。最小循环节为自身长度的串显然是好的。

那么，最小循环节长度为 $n$ 和 $1$ 的情况可以直接特判掉，剩下情况而言：

假设最小循环节长度为 $x$，我们显然可以直接把第一位断开，变成一个字符和一个后缀。后缀很明显不会有循环节，因为假设其循环节长度为 $m$，因为长度恰好是 $x$ 的倍数减一，所以不会是 $x$ 的倍数。那么就能推出答案存在 $\gcd(x,m)<x$ 的循环节，和假设矛盾。所以后一个显然不是循环的，那么显然可以分成两段解决。

分成两段解决就很方便了，只要枚举断开的位置然后判断两边是否都不循环即可。这就需要我们对前缀和后缀求最小循环节。

这个很好求，对于所有前缀枚举其所有因子 $d$，预处理出来，因为调和级数总数是 $n\log n$ 的。然后我当前要有大小为 $d$ 的循环节，需要 $i-d$ 前缀的也有。那么就是 $i-d$ 的前缀的最小循环节需要是 $d$ 的因数。然后还需要判断 $s[1,d]$ 和 $s[i-d+1,i]$ 是否相同，因为是和前缀判断，所以既可以用 Z 函数也可以用哈希。

倒过来再做一遍，就可以解决了。注意这题也卡哈希和效率，写哈希的话还是要自然溢出+特殊 Base。

ABC303G - Bags Game

我们可以设 $dp_{l,r}$ 表示当前剩下的球区间是 $[l,r]$，先手的贡献是正的的最终答案。

然后我们考虑转移，对于第一种转移，直接左边或者右边缩一个单位。

第二种转移和第三种转移本质是相同的，只是换了个数，这里只讨论第二种。

对于 $r-l+1\ge b$，就直接取走，求前缀和，贡献是 $s_r-s_{l-1}-a$。

否则，实际上我们就是要在 $[l,r]$ 中选择一个长度为 $len=r-l+1-b$ 的子区间 $[x,y]\subseteq[l,r]$，贡献是 $-dp_{x,y}+s_r-s_y+s_{x-1}-s_{l-1}$。我们把其中的贡献拆分开，就是 $\max\{-dp_{x,len+x-1}-s_{x+len-1}+s_{x-1}\}+s_r-s_{l-1}$。我们发现，区间长度恒定，区间左端点落在 $[l,r-len+1]$ 中，这是一个 rmq 问题。我们可以对所有的区间长度处理出关于区间左端点的 $-dp_{x,len+x-1}-s_{x+len-1}+s_{x-1}$。然后用 st 表查询。

直接 dp 输出答案即可，复杂度 $O(n^2\log n)$，st 表加区间操作，常数比较小。注意上一个人的答案在转换先后手之后要取反。

标签：子串,前缀,复杂度,28,枚举,哈希,字符串,杂题,log
From： https://www.cnblogs.com/jucason-xu/p/17440273.html