题目：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("%d\n",d); } } return 0; }
CF 914F Substrings in a String——bitset处理匹配
原文：https://www.cnblogs.com/Narh/p/10426333.html