參考博客：點擊打開鏈接

字符串hash典例。 這里用的是bkdrhash 法。也是最常用的沖突最少的一種。原理：把字符串和數(shù)值對應。這里用base=31(一般用質(zhì)數(shù))，

先是掃一遍，處理處每個位子到結(jié)尾構(gòu)成的串的hash值（倒過來的），然后長度為l的子串的haash值就好算了。

之后枚舉開頭l個，每次向后翻滾，復雜度max（L*M, L*(S.SIZE/M)）可以過，這里用了map判重下。若枚舉開頭掃一遍，姿勢不優(yōu)越過不了，極限可能：m=50000,l=1，復雜度(s,size*m)會超時。?

關(guān)鍵一：那里求hash值的時候+1，否則100,10這種hash值一樣。

開始擔心這樣減hash值會因為爆出現(xiàn)負值。其實不然：其一， ?unsigned long long ，自動取模 ? ???? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

其二：因為每次從后面向前推導：hash[i] = hash[i+1]*base+s[i]-‘a(chǎn)‘+1; ,本質(zhì)自動取模，所以：hash[i]=s[i]-‘a(chǎn)‘+1+hash[i+l]*nbase[l]?（每步自動取模）,由于?s[i]-‘a(chǎn)‘+1? 非負，所以有 ??

hash[i]>hash[i+l]*nbase[l] ? ? ? ? ? ? ?

? ?WA:

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 100050; const int seed = 31; int l,m; unsigned long long base[maxn],h[maxn],seq[maxn],ans[maxn]; char str[maxn];int calc(int left,int len) {int right = left + len - 1;return h[left] - h[right+1]*base[len]; }int main() { base[0] = 1;for(int i = 1; i <= maxn; i++)base[i] = base[i-1]*seed;while(scanf("%d%d",&m,&l)!=EOF){getchar();scanf("%s",str);int len = strlen(str);h[len] = 0;for(int i = len-1; i >= 0; i--)h[i] = h[i+1]*seed + str[i] - 'a' + 1;memset(seq,0,sizeof(seq));memset(ans,0,sizeof(ans));for(int i = 0; i < m; i++) ans[i] = 1;for(int i = 0; i < len - m; i++){int key = calc(i,m);seq[i] = key;if(i < m) continue;if(seq[i] != seq[i-m])ans[i] = ans[i-m] + 1;}int sum = 0;for(int i = 0; i < len; i++)if(ans[i] >= l)sum += ans[i] - l + 1;printf("%d\n",sum);}return 0; }

AC:

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<string> typedef unsigned long long ull; using namespace std; const int maxn= 100050; const ull base =31; ull nbase[maxn],hash[maxn]; int m,l; map<ull, int> mp; int main() {ull tmp;nbase[0] = 1;for (int i = 1;i<maxn; i++){nbase[i]=nbase[i-1]*base;}while (~scanf("%d%d",&m,&l)){string s;cin>>s;int slen=s.size();hash[slen] = 0;for (int i = slen-1; i >= 0; i--)hash[i] = hash[i+1]*base+s[i]-'a'+1; //關(guān)鍵1int ans = 0;for (int i = 0; i<l&&i+m*l<=slen; i++){mp.clear();for (int j = i; j<i+m*l; j += l){tmp = hash[j] - hash[j+l]*nbase[l];mp[tmp]++;}if (mp.size() ==m)ans++;for (int j=i+m*l; j+l<=slen; j +=l){tmp = hash[j-m*l] - hash[j-(m-1)*l]*nbase[l];mp[tmp]--;if (mp[tmp] == 0)mp.erase(tmp);tmp = hash[j] - hash[j+l]*nbase[l];mp[tmp]++;if (mp.size() == m)ans++;}}printf("%d\n", ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4821 字符串hash的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。