【Codeforces】 CF914F Substrings in a String

题目链接

CF方向
Luogu方向

题目解法

又学会了一种字符串匹配 + 骗分技巧！！！

用 $bitset$ 也可以字符串匹配！！！
考虑询问的字符串的总长度只有 $10^5$，所以可以考虑 $\frac{n^2}{\omega }$ 的做法
考虑从前往后遍历查询字符串，然后只要把之前匹配的结果往后移一位，然后 $\&$ 当前字符的出现位置即可
时间复杂度 $O(\frac{n^2}{\omega })$
有些边界情况需要特判

#include 
using namespace std;
const int N=100100;
char str[N],y[N];
bitset<N> bs[26];
int main(){
	scanf("%s",str+1);
	int n=strlen(str+1);
	for(int i=1;i<=n;i++) bs[str[i]-'a'][i]=1;
	int q;scanf("%d",&q);
	while(q--){
		int op,x;scanf("%d%d",&op,&x);
		if(op==1){
            scanf("%s",y);
			bs[str[x]-'a'][x]=0,bs[y[0]-'a'][x]=1;
			str[x]=y[0];
		}
		else{
			int z;scanf("%d%s",&z,y+1);
			int len=strlen(y+1);
			bitset<N> cur;cur.set();
			for(int i=1;i<=len;i++) cur=(cur<<1)&bs[y[i]-'a'];
            x+=len-1;
            if(x>z){ puts("0");continue;}
			cur>>=x;int ans=cur.count();
			cur>>=(z-x+1);ans-=cur.count();
			printf("%d\n",ans);
		}
	}
	fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33