lessons/参考实现/03-Bitset/CodeForces-914F.cpp

#include <bitset>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    constexpr int max_n = 100000;
    string s; cin >> s;
    vector<bitset<max_n>> position(26);
    for (int i = 0; i < static_cast<int>(s.size()); ++i) position[s[i] - 'a'].set(i);
    int q; cin >> q;
    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int i; char c; cin >> i >> c; --i;
            position[s[i] - 'a'].reset(i);
            s[i] = c;
            position[s[i] - 'a'].set(i);
        } else {
            int l, r; string y; cin >> l >> r >> y; --l; --r;
            int valid = r - l - static_cast<int>(y.size()) + 2;
            if (valid <= 0) { cout << "0\n"; continue; }
            bitset<max_n> match;
            match.set();
            for (int j = 0; j < static_cast<int>(y.size()); ++j) {
                match &= position[y[j] - 'a'] >> j;
            }
            match >>= l;
            match <<= max_n - valid;  // 只保留移位后下标 [0, valid-1]
            cout << match.count() << '\n';
        }
    }
}