找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1785|回复: 0
收起左侧

[米群网刷题小分队] [PAT-TOP] 1005. Programming Pattern

[复制链接]
发表于 5-3-2015 03:17 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
1005 Programming Pattern
这个题,就是给定一个长度在2^20内的字符串,并且再给一个长度m, 求所有长度为m的子串中出现次数最多的,如果有多个,输出字典序最小的。

直接滑动窗口map string,不行,因为比如m = 2 ^ 19 的子串也有2 ^ 19个,所以总共map的话,字符个数达到2^38太大了。。。于是用猥琐的BM算法,做滑动窗口hash, 质数权选的是17, 表大小选的是1299817 (也是质数)。之前选的31和1048601会挂掉一组数据 (97和1299817也会挂)——因为我hash根本没处理冲突,考rp的题。。。还有就是hash的value最终取起点就好了,因为没必要存字符串,起点和m自动构成一个字符串。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <string>
  4. #include <vector>

  5. using namespace std;

  6. const int W = 17 ;
  7. const int M = 1299817;

  8. char s[M];
  9. char answer[M];

  10. vector<pair<int,int> > have[M];

  11. int mul(long long x, long long y) {
  12.         return x * y % M;
  13. }

  14. int main() {G
  15. int m;
  16.         scanf("%d", &m);
  17.         gets(s);
  18.         gets(s);
  19.         int h = 0;
  20.         int w = 1;
  21.         int n = strlen(s);
  22.         for (int i = 0; i < m; ++i) {
  23.                 h = mul(h, W);
  24.                 h += (unsigned int) s【i】;
  25.                 if (h >= M) {
  26.                         h -= M;
  27.                 }
  28.                 if (i) {
  29.                         w = mul(w, W);
  30.                 }
  31.                
  32.         }
  33.         have[h].push_back(make_pair(0, 1));       
  34.         int num = 1;               
  35.         for (int i = 1; i + m <= n; ++i) {
  36.                 h -= mul((unsigned int) s[i - 1], w);
  37.                 if (h < M) {
  38.                         h += M;
  39.                 }
  40.                 h = mul(h, W);
  41.                 h += (unsigned int) s[i + m - 1];
  42.                 if (h >= M) {
  43.                         h -= M;
  44.                 }
  45.                 if (have[h].empty()) {
  46.                         have[h].push_back(make_pair(i, 1));
  47.                 }
  48.                 else {
  49.                         num = max(num, ++have[h][0].second);
  50.                 }
  51.         }
  52.         for (int i = 0; i < M; ++i) {
  53.                 if (!have【i】.empty() && (have【i】[0].second == num) && ((answer[0] == 0) || (strncmp(answer, s + have【i】[0].first, m) > 0))) {
  54.                         strncpy(answer, s + have【i】[0].first, m);
  55.                 }
  56.         }
  57.         printf("%s %d\n", answer, num);
  58.         return 0;
  59. }
复制代码


本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表