经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C » 查看文章
BZOJ4503: 两个串(bitset字符串匹配)
来源:cnblogs  作者:自为风月马前卒  时间:2018/10/11 9:26:56  对本文有异议

题意

题目链接

Sol

Orz xudyh

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

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

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

复杂度:\(O(\frac{n^2}{32})\)

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 1e5 + 10;
  4. int N, M, cnt;
  5. char S[MAXN], T[MAXN];
  6. bitset<MAXN> B[28];
  7. main() {
  8. scanf("%s\n%s", S + 1, T + 1);
  9. N = strlen(S + 1); M = strlen(T + 1);
  10. for(int i = 1; i <= N; i++) B[S[i] - 'a'].set(i);
  11. bitset<MAXN> ans; ans.set();
  12. for(int i = 1; i <= M; i++) if(T[i] != '?') ans &= (B[T[i] - 'a'] >> (i - 1));
  13. for(int i = 1; i <= N - M + 1; i++) if(ans[i] == 1) cnt++; printf("%d\n", cnt);
  14. for(int i = 1; i <= N - M + 1; i++) if(ans[i] == 1) printf("%d\n", i - 1);
  15. }
  16. /*
  17. ababababba
  18. a?aba?abba
  19. */
 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号