题目：[CF914F] Substrings in a String
这个题是这样的：
给你一个字符串 \(s\)，共有 \(q\) 次操作，每个都是下面两种形式的一种。
-
1 i c：将字符串 \(s\) 的第 \(i\) 项变为字符 \(c\)。 -
2 l r y：求字符串 \(y\) 在字符串 \(s\) 中以第 \(l\) 项为起点，以第 \(r\) 项为终点的子串（第 \(l\) 和第 \(r\) 项）中作为子串出现的次数。
\(1\leq |s|\leq 10^5\)，\(1\leq q\leq 10^5\)，\(\sum |y| \leq 10^5\)。
这个题的做法是这样的：
首先暴力的做法，可以做到 \(O(1)\) 的修改操作，以及通过通过枚举左端点然后暴力匹配的 \(O(|s|\cdot|y|)\) 的查询操作。
另一个方向是逐位思考，我们对字符串 \(y\) 的每一位来找到左端点，然后对这 \(|y|\) 个左端点的集合取交操作，最终集合中的个数就是其答案。
对集合取交的操作，可以想到用位运算 & 来做，那么就可以用 bitset 来做，得到了 \(O(\frac{|s|\cdot|y|}{w})\) 的复杂度。
虽然那个暴力在 \(|s|=|y|\) 的时候，可以有 \(O(|s|)\) 的复杂度。
参考代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
char s[N + 10], t[N + 10], c;
int n, m, qn;
bitset<N + 10> ans, ch[26];
int main()
{
cin >> (s + 1) >> qn;
n = strlen(s + 1);
for (int i = 1; i <= n; i ++ ) ch[s[i] - 'a'].set(i, true);
for (int _ = 1, opt, x, y; _ <= qn; _ ++ ) {
cin >> opt ;
if (opt == 1) {
cin >> x >> c;
ch[s[x] - 'a'].set(x, false);
ch[(s[x] = c) - 'a'].set(x, true);
}
else {
cin >> x >> y >> t;
ans.set();
if ((m = strlen(t)) > y - x + 1) {cout << 0 << '\n'; continue;}
for (int i = 0; i < m; i ++ ) ans &= (ch[t[i] - 'a'] >> i);
cout << (ans >> x).count() - (ans >> (y - m + 2)).count() << '\n';
}
}
return 0;
}