2013 Asia Regional Changchun I 题，HDU(4821)，Hash-白红宇

2013 Asia Regional Changchun I 题，HDU(4821)，Hash

阅读量：4630 次

发布时间：2019-06-09

本文共 2106 字，大约阅读时间需要 7 分钟。

题目链接：

解题报告：搞了很久，总算搞出来了，还是参考了一下网上的解法，的确很巧，和上次湘潭的比赛中的一个求平方和的题目思路很类似。

首先说一下hash，简单来说就是y = hash(x)，有很多函数，可以参考这里：

然后，我用的是这个：写法简单，而且重复的可能较小。

// BKDR Hash Functionunsigned int BKDRHash(char *str){    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..    unsigned int hash = 0;    while (*str)    {        hash = hash * seed + (*str++);    }    return (hash & 0x7FFFFFFF);}

然后回到这个题目：

3W,4RE,3TLE,首先wa的原因：循环次数少了一，<=slen,超时没办法，只能优化了。

下面是没有优化的代码，每个子串求一下hash.

/*#include 
     
      #include 
      
       #include 
       
        using namespace std;const int inf = 2000000;bool t[2000000];int Hash[100005];long long myhash(char *str){    int seed = 31;    long long hash = 0;    while (*str)        hash =( hash * seed + (*str++)-'a' + 1) %inf ;    return hash;}int main(){    int m,l;    while(scanf("%d%d",&m,&l)!=EOF)    {        char str[100005];        scanf("%s",str);        int len = strlen(str);        int ans = 0;        int k = 0;        for(int i=0; i+m

优化方案。上图比较好！！！

优化的位置就是成段删掉，成段添加。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         using namespace std;const int MAXN = 100010;const unsigned long long base = 31;unsigned long long nbase[MAXN],Hash[MAXN];int n,len,ans,slen;char str[MAXN];map
          
            mp;int main(){ unsigned long long tmp; nbase[0] = 1; for (int i = 1; i <= MAXN; i++) nbase[i] = nbase[i-1] * base; while (scanf("%d%d", &n, &len) != EOF) { scanf("%s", str); slen = strlen(str); Hash[slen] = 0; for (int i = slen-1; i >= 0; i--) Hash[i] = Hash[i+1]*base+str[i]-'a'+1; ans = 0; for (int i = 0; i < len && i+n*len <= slen; i++) { mp.clear(); for (int j = i; j < i+n*len; j += len) { tmp = Hash[j] - Hash[j+len]*nbase[len]; mp[tmp]++; } if (mp.size() == n) ans++; for (int j = i+n*len; j+len <= slen; j += len) { tmp = Hash[j-n*len] - Hash[j-(n-1)*len]*nbase[len]; mp[tmp]--; if (mp[tmp] == 0) mp.erase(tmp); tmp = Hash[j] - Hash[j+len]*nbase[len]; mp[tmp]++; if (mp.size() == n) ans++; } } printf("%d\n", ans); } return 0;}