Codeforce 941 F - Substrings in a String

February 21, 2020

941views

1446 words

Bitset

给定一个字符串$s$，一个区间$l,r$和一个字符串$y$
求s串的l,r区间内y的出现次数
用bitset来做,先开26个bitset对应26个小写字母,每个bitset保存其对应字符出现的位置。
我们要求$y$串出现次数，先求$y[0]$出现次数，再求$y[0-1]$出现次数，再求...$y[0-len-1]$出现的次数。求$y[0-i]$的出现次数肯定是求$y[0-(i-1)]$次数中满足$y[0-(i-1)]$后面紧跟$y[i]$的串的个数.
先初始一个$bitset$记为$ans$,初始全为1, 然后每次 $ans = ans&(bitset[y[i]-'a'] >> i )$ , 这个$ans$就是代表了串$y[0-i]$出现的次数，最后统计$ans$的区间$[l,r-len+1]$内有多少个$1$即可。不能暴力统计$1$的个数，会T。

```cpp

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
int n ,q;
char s[N] , y[N];
bitset<N> bs[30];
int main () {
    scanf("%s%d",s,&q);
    n = strlen(s);
    for(int i = 0;i < n; ++ i){
        bs[s[i] - 'a'].set(i);//保存每个字符出现的位置
    }
    int op , l ,r ;
    while(q--)
    {
        scanf("%d", &op);
        if(op == 1){
            scanf("%d%s",&l,y);
            -- l;
            bs[s[l] -'a'][l] = 0;
            s[l] = y[0];
            bs[s[l] -'a'][l] = 1;
        }
        else{
            scanf("%d%d%s",&l,&r,y);
            -- l ,-- r;
            int len = strlen(y);
            if(r - l + 1 < len) {
                puts("0");
                continue;
            }
            bitset<N> ans;
            ans.set();
            for(int i = 0; i < len ; ++ i){
                ans &= (bs[y[i]- 'a'] >> i);
            }
            int cnt = (ans >> l).count() - (ans >> (r - len + 2)).count();//不能暴力统计，要用前缀和思想
            printf("%d\n",cnt);

}

}
	return 0;
}

```

Last modification：February 21st, 2020 at 12:18 pm

如果觉得我的文章对你有用，请随意赞赏

Codeforce 941 F - Substrings in a String