题面
求模板串 $S$ 在 $T$ 中的出现次数。
其中 $1 \le |S|, |T| \le 10^7$.
时间限制 $5$ 秒, 内存限制 $\mathbf{1}$ MB, 且输入只能读取一次.
题解
KMP 模板题
题目让你在一个空间受限的背景下, 进行流式字符串匹配. 本题无论模板串还是询问串都无法放进内存, 你必须流式的一个一个读取.
首先, 回忆 Rabin-Karp 算法是怎么样的. 它对模板串 $S$ 求了一个 hash 值, 然后使用滑动窗口 维护询问串所有长度 $S$ 的子串的 hash 值, 这里时间复杂度是 $O(|T|)$ 的, 但是空间复杂度是 $O(|S|)$ 的 (需要存下整个窗口, 以供删除开头的字符). 显然无法满足本题的要求.
官方题解的做法:
- 读入模板串 $S$, 计算出长度为 $\lfloor \sqrt{n} \rfloor$ 的前缀 hash 值和完整串的 hash 值, 时间复杂度 $O(|S|)$, 空间复杂度 $O(1)$;
- 读入询问串 $T$, 维护 $\lfloor \sqrt{n} \rfloor$ 大小的滑动窗口, 可以求出询问串中所有和这个根号前缀匹配的位置. 相当于, 筛出去了一些必不可能匹配上的位置, 留下来一些位置需要求出相应的全长度的 hash 值.
- 注意到, 直到这里实际上还没有本质的改善, 一是匹配上的位置仍然很多, 二是难以搞出相应的全串 hash 值.
- 根据 (Weak) Periodicity Lemm, 我们可以把匹配上的位置分成至多 $\lceil \sqrt{n} \rceil$ 组等差数列. 具体的, 每组中所有匹配的子串是一个顺次有重叠的列表, 相邻出现位置的距离差相等 (也就是所谓的构成等差数列, 进一步, 重叠部分其实就是根号前缀的 border). 于是, 记录匹配位置的空间被压缩到了 $O(\lfloor \sqrt{n} \rfloor)$.
- 下一个问题是, 我们不仅需要记录匹配的位置, 还需要记录匹配处的前缀 hash 值, 等到处理到该次可能匹配的结束位置时来进行全串的比对. 同样根据上述引理的结论, 同一组等差数列内部, 相邻 2 个匹配位置之间的 hash 值是固定的, 我们只需要记录等差数列的起点, 公差, 终点, 起点的 hash 值, 公差对应字符串部分的 hash 值, 就能表示出这一个等差数列的所有位置信息和 hash 值信息.
最终, 时间复杂度 $O(n)$, 空间复杂度 $O(\lfloor \sqrt{n} \rfloor)$, 一是维护滑动窗口, 二是维护所有等差数列.