知识点：bitset，SAM，根号分治
Link：https://codeforces.com/problemset/problem/914/F
一种在字符集较小情况下的多轮字符串匹配暴力的优化。
好久没写过单题的题解了格式都忘了、、、
简述
给定一仅包含小写字母的字符串 \(s\)，给定 \(q\) 次操作，每次操作都是下列两种形式之一：
- 将字符串给定位置 \(s_i\) 修改为字符 \(c\)。
- 给定参数 \(l, r\) 和字符串 \(t\)，询问 \(s\) 的子串 \(s[l : r]\) 中字符串 \(t\) 出现的次数。
\(1\le |s|\le 10^5\)，\(1\le q\le 10^5\)，\(\sum |t|\le 10^5\)。
6S，256MB。
分析
正经做法
\(\sum |t| \le 10^5\) 是非常重要的性质，望周知。
正经做法是考虑对字符串分块，对每块建 SAM，对于修改操作则暴力重构该块的 SAM，对于查询操作考虑被查询字符串长度 \(|t|\) 和块长 \(k\) 的关系：
- 若 \(|t|\ge k\)，则此类询问最多出现 \(\frac{\sum |t|}{k}\) 次，考虑每次暴力建出子串 \(s[l:r]\) 的 SAM 并匹配即可。处理此类询问所需时间复杂度上界为 \(O\left(n \times \frac{\sum |t|}{k} + \sum |t|\right)\) 级别。
- 若 \(|t|\le k\)，则分别考虑位于整块内的 \(t\) 和跨越两块的 \(t\)。位于整块内的直接在区间内的所有 SAM 上匹配；跨越两块的同样考虑暴力，对区间内相邻的两块分界线附近长度为 \(2\times |t|\) 的部分建出 SAM（或 KMP）并匹配。需要暴力建 SAM（或 KMP）的区间长度总和上限为 \(\sum \left(2\times \frac{n}{k}\times |t|\right)\le 2\times n\) 级别，则处理此类询问所需时间复杂度上界为 \(O\left(2\times n + \sum\left(\frac{n}{k}\times|t|\right)\right)\) 级别。
发现 \(n\) 和 \(\sum |t|\) 同级，当 \(k=\sqrt n\) 级别时总时间复杂度为 \(O\left(n\sqrt n\right)\) 级别，又给了 6S，感觉就能过了。
然而很难写并且需要大力卡常还要玄学调块长、、、
虽然思路挺一眼的但反正我是没写，吸吸。
为什么不全用 KMP 呢？因为 KMP 匹配复杂度是和原串长度有关的，而 SAM 只与匹配串长度有关，因为只保证了 \(\sum |t|\le 10^5\) 所以只能用 SAM。
不正经做法
然后是不正经但是爆踩标算做法。为了把常数超大的正解放过去给的超大时限就是用来乱搞的吸吸
发现字符集较小，有一种对较小字符集做子串匹配的 bitset 搞法。
开 26 个 bitset，记 \(f_{i, j} = [s_{j} = i]\)，按顺序考虑匹配串 \(t\)（\(i\) 从 0 开始计数）的每一位：
- 对于满足 \(f_{t_0, j}=1\) 的位置 \(j\)，子串 \(s[j:]\) 可以与 \(t\) 至少匹配 1 位。
- 对于满足 \(f_{t_0, j} = 1 \land f_{t_1, j + 1} = 1\) 的位置 \(j\)，子串 \(s[j:]\) 可以与 \(t\) 至少匹配 2 位。
- ……
- 对于满足 \(f_{t_0, j} = 1 \land \dots \land f_{t_{|t| - 1}, j + |t| - 1} = 1\) 的位置 \(j\)，子串 \(s[j : j + |t| - 1]\) 可以与 \(t\) 匹配。
上述过程实际上是在对位置的集合不断地取子集，显然可以通过维护的 bitset 实现。按照上述规则手玩一下发现所有匹配的位置即为 f[t[i]] >> i 的交。此时直接统计 f[t[i]] >> i 中 1 的个数即得整个原串中所有匹配位置。在此基础上再对 bitset 进行右移后作差即得区间内匹配位置。
特别地，要注意特判被匹配区间短于匹配串的情况。
修改 \(O(1)\) 级别，总时间复杂度上界为 \(O\left(\sum |t|\times \frac{|s|}{w}\right)\) 级别。
但是跑了 2.7S 吸吸
代码
不正经做法：
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n, q;
char s[kN];
std::bitset <kN> appear[26], ans;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::cin >> s + 1; n = strlen(s + 1);
for (int i = 1; i <= n; ++ i) appear[s[i] - 'a'].set(i);
q = read();
while (q --) {
int opt = read();
if (opt == 1) {
int pos; char val;
std::cin >> pos >> val;
appear[s[pos] - 'a'].reset(pos);
s[pos] = val;
appear[s[pos] - 'a'].set(pos);
} else {
int l, r; std::string t;
std::cin >> l >> r >> t;
if (t.size() > r - l + 1) {
std::cout << "0\n";
continue;
}
ans.set();
for (int i = 0, sz = t.size(); i < sz; ++ i) ans &= appear[t[i] - 'a'] >> i;
std::cout << (ans >> l).count() - (ans >> (r - t.size() + 2)).count() << '\n';
}
}
return 0;
}