F. Substrings in a String codefoces 941 F bitset | shift-and 算法

给定一个小写字符组成的字符串S，（|S|<1e5，下标从1开始）,现在有Q种操作，对于每个操作Q(Q<=1e3)，输入opt，

如果opt==1，输入x，c，表示把S[x]改为c，（c是小写字母）。

如果opt==2，输入字符串T，输出S种有多少个字串==T（字串可以重叠）,（|T|<=10）。

inputCopy
ababababa
3
2 1 7 aba
1 5 c
2 1 7 aba
outputCopy
3
1

mycode：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
char Mu[maxn];
  char tmp[maxn];
bitset<maxn>o[27],ans;
int main()
{
    scanf("%s",Mu+1);
    int len = strlen(Mu+1);
    for(int i=1;i<=len;i++)
    {
        o[Mu[i]-'a'].set(i);
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int op;
        cin>>op;

        int pos;
        if(op==1)
        {
            scanf("%d%s",&pos,tmp);
            o[Mu[pos]-'a'][pos] = 0;
            Mu[pos] = tmp[0];
            o[tmp[0]-'a'][pos] = 1;
        }
        else
        {
            int l,r;
            cin>>l>>r;
            scanf("%s",tmp);
            int S = strlen(tmp);
            if(S>(r-l+1))
            {
                printf("0\n");
                continue;
            }
            ans.set();
            for(int i=0;i<S;i++)
            {
                ans&=(o[tmp[i]-'a']>>i);
                //错位与，累计在起点位置
            }
            //bitset第0位不用，加上前缀，进行计算
            printf("%d\n",(ans>>l).count()-(ans>>(r-S+2)).count());
        }
    }
    return 0;
}

输出思考版：

#include<bitset>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10;
bitset<maxn>s[27],ans;
char a[maxn],b[maxn],c[3];
void read(int &res)
{
    char c=getchar();
    while(c>'9'||c<'0') c=getchar();
    for(res=0;c>='0'&&c<='9';c=getchar()) res=(res<<3)+(res<<1)+c-'0';
}
int main()
{
    scanf("%s",a+1);
    int T=strlen(a+1);
    int i,j,l,r,Q,opt;
    for(i=1;i<=T;i++)
        s[a[i]-'a'].set(i);
    read(Q);
    for(i=0;i<=25;i++)
    cout<<s[i]<<"*i"<<endl;
    cout<<endl;
    while(Q--){
        read(opt);
        if(opt==1){
            scanf("%d%s",&j,c);
            s[a[j]-'a'][j]=0;
            s[(a[j]=c[0])-'a'][j]=1;
        }
        else {
            read(l); read(r);
            scanf("%s",b);
            int S=strlen(b);
            if(S>r-l+1) {
                 puts("0"); continue;
            }
            ans.set();
            cout<<ans<<"*1"<<endl;
            for(i=0;i<S;i++){
                ans&=(s[b[i]-'a']>>i);ftjm   gc
                cout<<(s[b[i]-'a']>>i)<<endl;
                cout<<ans<<endl;
                cout<<endl;
            }
            cout<<ans<<"*2"<<endl;
            printf("%d\n",(ans>>l).count()-(ans>>(r-S+2)).count());
            cout<<(ans>>l)<<" 77"<<(ans>>(r-S+2))<<endl;
        }
    }
    return 0;
}