首页 > 代码库 > 2013 Asia Regional Changchun I 题,HDU(4821),Hash

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

题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=4821

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

首先说一下hash,简单来说就是y = hash(x),有很多函数,可以参考这里:https://www.byvoid.com/blog/string-hash-compare/

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

// 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 <cstdio>#include <cstring>#include <string>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<len; i++)        {            char temp[100005];            for(int j=0; j<l; j++)                temp[j] = str[i+k*m+j];            temp[l] = ‘\0‘;            long long hashs = myhash(temp);            Hash[i+k*m] = myhash()        }        for(int i=0; i<l&&i+m*l<=len; i++)        {            memset(t,false,sizeof(t));            bool flag = true;            for(int k = 0; k<m; k++)            {                char temp[100005];                for(int j=0; j<l; j++)                    temp[j] = str[i+k*m+j];                temp[l] = ‘\0‘;                long long hashs = myhash(temp);                if(t[hashs])                {                    flag = false;                    break;                }                t[hashs] = true;            }            if(flag) ans++;        }        printf("%d\n",ans);    }    return 0;}*/

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

技术分享

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

 

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <map>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<unsigned long long, int> 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;}

 

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