CF914F Substrings in a String

Description

给你一个字符串ss，共有qq次操作，每个都是下面两种形式的一种。

11 ii cc

这个操作表示将字符串ss的第ii项变为字符cc

22 ll rr yy

这个操作表示输出字符串yy在字符串ss中以第ll项为起点，以第rr项为终点的子串（包括第ll和第rr项）中作为子串出现的次数。

Solution

和BZOJ 4503一样

稍微改改

Code

#include <bitset>

#include <string>

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

const int N = 100005;

std:: bitset<N> A[26];

int main () {

    std:: string S;

    std:: cin >> S;

    for (int i = 0; i < S.size(); i += 1)

        A[S[i] - 'a'].set(i);

    int n;

    scanf("%d", &n);

    std:: string str;

    while (n --) {

        int opt, l, r;

        scanf("%d%d", &opt, &l);

        l -= 1;

        if (opt == 1) {

            std:: cin >> str;

            A[S[l] - 'a'].reset(l);

            S[l] = str[0];

            A[S[l] - 'a'].set(l);

        }

        else {

            scanf("%d", &r);

            r -= 1;

            std:: cin >> str;

            std:: bitset<N> res;

            res.set();

            for (int i = 0; i < str.size(); i += 1)

                res &= (A[str[i] - 'a'] >> i);

            r = r - str.size() + 1;

            printf("%d\n", std:: max(0, (int)((res >> l).count() - (res >> r + 1).count())));

        }

    }

    return 0;

}