BZOJ4503: 两个串(bitset字符串匹配)
程序员文章站
2022-05-15 20:31:07
题意 "题目链接" Sol Orz xudyh F个毛T啊。。直接bitset一波就赢了啊。。。(~~虽然复杂度很假~~) 就是记录匹配串中每个元素出现的位置,将第$i$个位置的bitset右移$i$位后与起来 最后找1出现的位置就行了 复杂度:$O(\frac{n^2}{32})$ cpp inc ......
题意
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 */