CF 914F Substrings in a String——bitset处理匹配

发布时间：2020-12-14 04:23:22 所属栏目：大数据来源：网络整理

导读：题目：http://codeforces.com/contest/914/problem/F 可以对原字符串的每种字母开一个 bitset 。第 i 位的 1 表示这种字母在第 i 位出现了。考虑能不能匹配上，可以把可行的 “开头” 设成 1 ；这样的话，枚举到匹配串的第 i 位，字符是 ch，就找出原字符

题目：http://codeforces.com/contest/914/problem/F

可以对原字符串的每种字母开一个 bitset 。第 i 位的 1 表示这种字母在第 i 位出现了。

考虑能不能匹配上，可以把可行的 “开头” 设成 1 ；

这样的话，枚举到匹配串的第 i 位，字符是 ch，就找出原字符串里 ch 对应的那个 bitset ，则 bt[ ch ] >> ( i-1 ) 的这些位置可以是合法的开头；

所以每次 ans 每个位置都赋成 1 ，然后对于匹配串的每个位置， & 一下 bt[ ch ] >> ( i-1 ) ，最后看看对应区间里有几个合法的开头就行啦！

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
using namespace std;
const int N=1e5+5,K=30;
int n; char s[N],ch[N];
bitset<N> bt[K],ans,ini;
int main()
{
  scanf("%s",ch+1); n=strlen(ch+1);
  for(int i=1;i<=n;i++)
    bt[ch[i]-‘a‘][i]=1;
  for(int i=1;i<=n;i++)ini[i]=1;
  int Q,op,u,l,r,m; char tp[5];
  scanf("%d",&Q);
  while(Q--)
    {
      scanf("%d",&op);
      if(op==1)
    {
      scanf("%d",&u);scanf("%s",tp);
      bt[ch[u]-‘a‘][u]=0;
      ch[u]=tp[0];
      bt[ch[u]-‘a‘][u]=1;
    }
      else
    {
      scanf("%d%d",&l,&r);scanf("%s",s);
      ans=ini; m=strlen(s);
      if(m>r-l+1){puts("0");continue;}
      for(int i=0;i<m;i++)
        ans&=(bt[s[i]-‘a‘]>>i);
      int d=(ans>>l).count() - (ans>>(r-m+2)).count();
      printf("%dn",d);
    }
    }
  return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!