Steven_MengのBlog

传送门

$bitset$的神奇用法,乍眼一看好像是$KMP$,发现每次都要预处理$next$数组,时间复杂度爆了。

考虑$bitset$(玄学),我们记录这样一个$bitset$ $ a[i][j]$,其中$a[i][j]=1$时,$s[j]$-‘a’$=i$

大概把字符串$abcabcabc$能转换成这样一个东西:

a 1 0 0 1 0 0 1 0 0
b 0 1 0 0 1 0 0 1 0
c 0 0 1 0 0 1 0 0 1

修改非常简单,只要把原来的$1$变成$0$,再把新加进的变成$1$

考虑如何查询,假设我们查询的是$abc$,我们把$a,b,c$挪到同一列(用位移操作即可完成),如下:

a 1 0 0 1 0 0 1 0 0
b 1 0 0 1 0 0 1 0 0
c 1 0 0 1 0 0 1 0 0

用$ans$去和每一列做$and$运算,操作完之后,$ans$大概长成这个样子:

ans 1 0 0 1 0 0 1 0 0

发现只有在$i$位后面出现$abc$字符串,$ans[i]$才为$1$。

于是我们发现答案为$\sum_{i=l}^{r-len+1} ans[i]$($len$为查询的字符串的长度),前缀和相减即可。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 27
using namespace std;
bitset<MAXN>B[MAXM];
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
inline char gc(){
char ch=getchar();
while (ch<'a'||ch>'z') ch=getchar();
return ch;
}
int main(){
char ch[MAXN];
scanf("%s",ch);
int n=strlen(ch);
for (register int i=1;i<=n;++i){
B[ch[i-1]-'a'][i]=1;
}
int q=read();
while (q--){
int opr=read();
if (opr==1){
int i=read();
char c=gc();
B[ch[i-1]-'a'][i]=0;
ch[i-1]=c;
B[ch[i-1]-'a'][i]=1;
}
else {
int l=read(),r=read();
char y[MAXN];
scanf("%s",y);
int len=strlen(y);
bitset<MAXN>ans;
ans.set();//set是全部变成1
for (register int i=0;i<len;++i){
ans&=(B[y[i]-'a']>>i);
}
printf("%d\n",max(0,(int)(ans>>l).count()-(int)(ans>>(r-len+2)).count()));
}
}
}

听说正解是分块+$SAM$,害怕

 评论