【哈希】POJ 1200 Crazy Search

 POJ 1200 Crazy Search

  • 题意:有一个字符串,这个字符串中可能出现的不同字符数是nc,让我们求这个字符串中有多少个长度为n不同的子串(相信大噶应该都知道子串和子序列的区别的【不像我每次写博客都要去百度www,怕出锅qaq】)。
  •  You may assume that the maximum number of substrings formed by the possible set of characters does not exceed 16 Millions.【字符可形成的不同子串(根本就没有限定是输入的字符串)的最大个数不超过16 Million.】最后这个条件简直就是题眼啊www重要的一批。意思就是我们将字符串看成“大数”,那么大数的范围就是16e6。如果题目给的是211,那么也就是不同子串的个数不超过211啊,1、2、3、4、5、...、10、11这些都是不同子串。QAQ。开始就一直读错了,不知道这个范围到底是什么鬼。
  • 思路:我们将所有不同字符从1-nc编号,于是我们就是nc+1进制(nc进制也可以,但是毕竟是1-nc,0虽然没有用,但还是nc + 1进制的嘛),开一个vis[]数组记录某哈希值有没有出现过。然后我们扫一遍长度为n的子串,算出哈希值,然后记录ans即可。
  • 不知道有没有跟我一样没有用nc这个条件,直接上字符串匹配的karp-rabin算法模板。过不了的。我MLE过,也WA过。可能就是因为16M限制了我们必须要用nc进制。我直接用了27进制还是不对,可能27进制也卡了。
  • 还有就是set会T,set会T,set会T!!!!!!!qaq

FEELING:乍一看确实是哈希的嘛,一遍扫过去,哈希值有多少个就是多少个不同子串咯。首先就是直接用的字符串匹配的karp-rabin算法(自己定义的base,所以没有用到nc)。emmmMLE了,www. 后来看了这道题的discuss,上面说好好看题,就是用到了nc咯,于是又改成nc进制。还是不对啊WA了。后来就是搜题解,全部都是没有用区间求哈希值,也就是没有预处理。就是遍历的时候才算哈希值。然后开了一个vis数组。这时候问题就来了。这个vis数组开多大?为什么开了16e6就可?后来问了人吧,他的一句话点醒了我,因为我们是将字符串看成nc进制的“大数”,于是我们的子串个数就是大数范围有多大。比如说211,那么211的子串就有211个。反正我现在还是觉得这个题很诡异。搞不懂,想不明白。www

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define INF 0x3f3f3f3f
#define lowbit(x) x & (-x)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxN = 16000000 + 7;
const int base = 27;
int n, nc;
char s[maxN];
int disc[26];
bool vis[maxN];
void init()
{
    memset(disc, 0, sizeof(disc));
    memset(vis, false, sizeof(vis));
}
int main()
{
    while(~scanf("%d%d", &n, &nc))
    {
        init();
        getchar();
        scanf("%s", s);
        int len = strlen(s);
        int tot = 1;
        for(int i = 0; i < len; i ++ )
        {
            if(!disc[s[i] - 'a'])
                disc[s[i] - 'a'] = tot ++;
            if(tot > nc) break;
        }
        int ans = 0;
        for(int i = 0; i <= len - n; i ++ )//枚举长度为n的字符串的开头
        {
            int Hash = 0;
            for(int j = i; j < i + n; j ++ )
                Hash = Hash * tot + disc[s[j] - 'a'];
            if(!vis[Hash])
            {
                vis[Hash] = true;
                ans ++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

 

【哈希】POJ 1200 Crazy Search【哈希】POJ 1200 Crazy Search Eve_Miracle* 发布了191 篇原创文章 · 获赞 57 · 访问量 1万+ 私信 关注
上一篇:实现字符串和从0到n-1范围内的数字串的一一对应---->poj1200


下一篇:背包问题-多重背包