题意：
给定长度为n的串S和长度为m的串T，还有一个整数k 串只由ACGT组成，问T串在S串中出现了多少次，匹配机制比较特殊： 定义T[i]能匹配上S[j]，当且仅当T[i]在S[j-k,j+k]中出现过，即存在偏移位差k
数据范围：n,m,k<=2e5
解法：
考虑没有偏移的时候怎么计算匹配数
,
可以KMP
,但是偏移之后就不行了
,
考虑用bitset计算匹配
:
对每个字符集单独考虑
,
假设当前选择字符为x
,
令S串中x字符为
1,其他字符为
0,那么变成一个
01串
,
对
4种字符处理就会得到
4个
01串
,A的
01串设为
bitset(A
).
开一个bitset
<N
>ans
,赋值为全
1,
遍历T串
,当遇到t
[i
]的时候
,ans
&=(bitset(t
[i
])>>(i
-1))
剩下来的
1表示t
[i
]可以被匹配的开头位置
,
遍历完之后
,还剩下的
1就是合法的开头位置了
.
每个字符可以被匹配的范围为
[i
-k
,i
+k
],
这个可以差分预处理出来
,然后也得到
4种
bitset()
然后按照上面的匹配做就行了
.
code：
#include<bits/stdc++.h>
using namespace std
;
const int maxm
=2e5+5;
char s
[maxm
];
char t
[maxm
];
int d
[4][maxm
];
int n
,m
,k
;
bitset
<maxm
>bit
[4],temp
;
signed main(){
map
<char,int>mp
;
mp
['A']=0;
mp
['C']=1;
mp
['G']=2;
mp
['T']=3;
scanf("%d%d%d",&n
,&m
,&k
);
scanf("%s",s
+1);
scanf("%s",t
+1);
for(int i
=1;i
<=n
;i
++){
s
[i
]=mp
[s
[i
]];
}
for(int i
=1;i
<=m
;i
++){
t
[i
]=mp
[t
[i
]];
}
for(int i
=1;i
<=n
;i
++){
d
[s
[i
]][max(1,i
-k
)]++;
d
[s
[i
]][min(n
,i
+k
)+1]--;
}
for(int i
=0;i
<4;i
++){
for(int j
=1;j
<=n
;j
++){
d
[i
][j
]+=d
[i
][j
-1];
if(d
[i
][j
]){
bit
[i
][j
]=1;
}
}
}
for(int i
=1;i
<=n
;i
++){
temp
[i
]=1;
}
for(int i
=1;i
<=m
;i
++){
temp
&=(bit
[t
[i
]]>>(i
-1));
}
int ans
=0;
for(int i
=1;i
<=n
;i
++){
ans
+=temp
[i
];
}
cout
<<ans
<<endl
;
return 0;
}
