前言
怎么题解区同质化这么严重，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：
其他的数据结构维护哈希（比如分块，平衡树）
只要是支持区间合并和区间加的数据结构就行。不过应该没人会写。