当前位置： 移动技术网 > IT编程>开发语言>C/C++ > BZOJ4503: 两个串(bitset字符串匹配)

BZOJ4503: 两个串(bitset字符串匹配)

2018年10月11日  | 移动技术网IT编程  | 我要评论

兽交配图,杨思卓,我想找个富婆

题意

题目链接

sol

orz xudyh

f个毛t啊。。直接bitset一波就赢了啊。。。(虽然复杂度很假)

就是记录匹配串中每个元素出现的位置，将第\(i\)个位置的bitset右移\(i\)位后与起来

最后找1出现的位置就行了

复杂度：\(o(\frac{n^2}{32})\)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, m, cnt;
char s[maxn], t[maxn];
bitset<maxn> b[28];
main() {
    scanf("%s\n%s", s + 1, t + 1);
    n = strlen(s + 1); m = strlen(t + 1);
    for(int i = 1; i <= n; i++) b[s[i] - 'a'].set(i);
    bitset<maxn> ans; ans.set();
    for(int i = 1; i <= m; i++) if(t[i] != '?') ans &= (b[t[i] - 'a'] >> (i - 1));
    for(int i = 1; i <= n - m + 1; i++) if(ans[i] == 1) cnt++; printf("%d\n", cnt);
    for(int i = 1; i <= n - m + 1; i++) if(ans[i] == 1) printf("%d\n", i - 1);
}
/*
ababababba
a?aba?abba
*/

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网