CF 914F Substrings in a String(bitset)

题目描述

https://codeforces.com/problemset/problem/914/F

简要题意：给定一个长度为 $n$ 的字符串 $S$，现在有 $m$ 次操作，操作有两种，第一种操作是给定一个整数 $x$ 和一个字符 $ch$，将 $S_x$ 改成 $ch$；第二种操作给定 $[l,r]$ 和字符串 $T$，求字符串 $T$ 在 $S[l..r]$ 中出现了多少次

$|S|,m,\sum |T|\le 10^5$

Solution

注意到数据范围全部是 $10^5$，我们直接考虑 $bitset$，第一个操作显然可以做到 $O(1)$，第二个操作我们直接做字符串匹配然后通过左移和右移把区间 $[l,r]$ 外的变成 $0$ 即可

时间复杂度 $O(\frac{n^2}{w})$

#include <iostream>
#include <bitset>
#include <cstring>
#define maxn 100010
#define ch(c) (c - 'a')
using namespace std;

int n, m;
char s[maxn], c[maxn];

const int N = 100000;
bitset<N + 1> B[26], ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr); 

    cin >> s + 1 >> m; n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) B[ch(s[i])].set(i);
    for (int i = 1; i <= m; ++i) {
        int opt, x, y, l; cin >> opt;
        if (opt == 1) {
            cin >> x >> c;
            B[ch(s[x])].reset(x);
            s[x] = c[0];
            B[ch(s[x])].set(x);
        } else {
            cin >> x >> y >> c + 1; l = strlen(c + 1);
            y = y - l + 1; if (x > y) { cout << 0 << "\n"; continue; } 
            ans.set();
            for (int i = l; i; --i) {
                ans &= B[ch(c[i])];
                if (i > 1) ans >>= 1;
            }
            ans = ans >> x << N + x - y;
            cout << ans.count() << "\n";
        }
    }
    return 0;
}