\(\text{CF1207G}\)
题目描述
有 \(n\) 次操作，每一次操作描述了第 \(i\) 个字符串，要么是单独一个字符，要是是在第 \(j\) 个字符串后拼接一个字符得到。
接下来又 \(m\) 次询问，每一次给出一个字符串问在第 \(i\) 个字符串中出现了多少次？
思路
考虑检出 \(\text{ACAM}\) 。一个字符串 \(s\) 在第 \(i\) 个字符串中出现了多少次就相当于问这个字符串的末尾节点在 \(fail\) 树的子树内有多少节点属于字符串 \(i\) 的。所以将询问离线下来，我们在 \(trie\) 树上dfs,同时维护 \(fail\) 树上的单点加，区间求和即可。
时间复杂度 \(O(n \log n)\) 。
\(\text{CF549E}\)
题目描述
给出 \(n\) 个字符串 \(s_1,s_2,...,s_n\) 。有 \(q\) 次询问，每一次询问问 \(s_k\) 在 \(s_l,...,s_r\) 中出现了多少次？
思路
我们不喜欢区间询问，所以把他拆分为了前缀询问，之后考虑离线。
对于一个字符串，我们暴力的将其在 \(fail\) 树上的全部节点到根的路径都增加 \(1\) 。询问就相当于单点查询。这可以使用树剖维护。
时间复杂度 \(O(n \log^2 n+q \log n)\) 。
\(\text{BOI2004 Repeats}\)
题目描述
现在有一个字符串 \(s\) ，希望求出一个子串 \(t\) 满足 \(\dfrac{|t|}{KMP_t}\) 尽量大。其中 \(KMP_t\) 表示字符串 \(t\) 的最小整周期。
思路点拨
我们考虑枚举 \(KMP_t\) 的长度 \(k\)，接下来枚举一个起点 \(i\) 。这时字符串 \(s[i,i+k-1]\) 的循环次数就是 \(1+\dfrac{LCP(suf_i,suf_{i+k})}{k}\) ，至于正确性读者画图就知道了。这样我们得到了 \(O(n^2)\) 的做法。
我们不需要枚举每一个起点，只需要枚举 \(i+xk\) 的这些端点就足够了。每一次使用后缀数组往前后扩展公共前后缀。更加具体而言，我们的扩展左端点是 \((i-1)-LCS(pre_i-1,pre_{i+k-1})+1\) ，扩展右端点是 \(i+LCP(suc_i,suc_{i+k})-1\) 。大家可以自己多多画图理解为什么。
\(LCP\) 和 \(LCS\) 使用后缀数组优化，时间复杂度 \(O(n \log n)\) 预处理加上 \(O(\sum_{i=1}^n \dfrac{n}{i})\) 求解就是 \(O(n \log n)\) 的。
\(\text{CF710F}\)
题目描述
维护一个字符串集合，支持如下操作：
- 增加一个字符串
- 删除一个字符串
- 给出一个字符串 \(s\) ,问集合中字符串在 \(s\) 中出现的次数和。
强制在线
思路点拨
如果不考虑空间的话，我们可以使用时间轴 \(\text{BIT}\) 套 \(\text{ACAM}\) 做到 \(O(n \log n)\) 的时间复杂度，但是空间复杂度为 \(O(26n \log n)\) ，所以是不可以通过的。
我们考虑优化空间，可以在增加字符串/删除字符串的时候维护 \(\text{BIT}\) 划分的变化（二进制分组），做到空间线性。
\(\text{KMP}\) 的特殊运用
\(\text{bitset}\) 优化字符串匹配
题目描述
现在有一个字符串 \(s\) ，需要支持如下操作：
-
字符串 \(s\) 单个位置的修改
-
给出一个字符串 \(t\) 问在 \(s\) 中出现的次数。
思路点拨
我们开 \(26\) 个桶，第 \(i\) 个桶存放了 \(s_j='a'+i-1\) 的下标 \(j\) 。
匹配维护可行的端点桶，每一次对相应的桶移位，取位运算与即可。过程使用 \(\text{bitset}\) 优化一下没什么好讲的。
时间复杂度 \(O(\dfrac{n^2}{w})\) ，空间复杂度 \(O(\dfrac{nS}{w})\) 。其中 \(S\) 表示字符集大小。
含有通配符的字符串匹配
题目描述
现在有两个字符串 \(s,t\) ，均有小写字母和通配符组成。通配符可以替换为任何字符，问 \(t\) 在 \(s\) 中出现的次数。
思路点拨
我们给每一个字符赋值，但是通配符的权值为 \(0\) 。字符串 \(s\) 的第 \(i\) 个位置权值 \(p(i)\) 定义为：
当 \(p(i)\) 等于 \(0\) 的时候就是一次匹配，大家可以根据赋值的方式理解一下。如果 $s_{i+j}=t_j $ ，那么 \((s_{i+j}-t_j)^2=0\) ；如果存在通配符，那么 \(s_{i+j}\) 和 \(t_j\) 中存在 \(0\) 。
考虑推一下式子：
这时三个不同的卷积，变换一下下标之后 \(NTT\) 即可。时间 \(O(n \log n )\) 。