前言
怎么题解区同质化这么严重,16 篇题解全是 差分 + KMP,就没有人写别的做法吗。
(好吧其实是我一开始没想到差分才有了这么多奇怪做法)
题目大意
给定两个序列 \(a,b\),求 \(b\) 在 \(a\) 中出现了多少次。
我们定义 \(b\) 在 \(a\) 的出现次数为:
\[\sum_{i=1}^n\left[\left(\sum_{j=1}^m[a_{i+j-1}-b_j=a_{i+j-1}-b_1]\right)=m\right] \]其中 \(n=|a|,m=|b|\)。
思路分析
- 做法 1:
将 \(a,b\) 分别差分,对两个差分数组做 KMP 字符串匹配,这也是其他所有题解的做 法。
时间复杂度为 \(O(n+m)\)。
- 做法 2:
直接对 \(a,b\) 分别哈希,得到哈希数组 \(f,g\),这里我们的哈希使用多项式哈希,也就是说
\[f_n=\left(\sum_{i=1}^np^{n-i}a_i\right)\bmod P \]那么我们判定 \(b\) 在 \(a\) 中出现一次的依据就是 \(\sum_{i=0}^{m-1}p^i\mid (f_{i+m-1}-p^{m}f_{i})-g_m\)。也就是从 \(i\) 开始的长为 \(m\) 的 \(a\) 的哈希值与 \(b\) 的全哈希值的差可以被 \(\sum_{i=0}^{m-1}p^i\) 整除。
时间复杂度为 \(O(n+m)\),常数稍大。
- 做法 3:
我们使用线段树维护哈希,每次 check 时先进行一次区间减操作,把二者的差值减掉,再比较区间和全串的哈希值,最后把差值加回去。
时间复杂度为 \(O(n\log n)\)。
- 做法 4:
差分 + 哈希。(跟 KMP 没什么区别)
- 做法 5:
其他的数据结构维护哈希(比如分块,平衡树)
只要是支持区间合并和区间加的数据结构就行。不过应该没人会写。