简单字符串hash,通过对字符串每个位置进行加权运算,使得后面每个字符的hash值都受前面字符的影响,从而将多个字节的字符串转化为整数,但有时会发生冲突。
关键部分:seed权值,通常是质数,如果太小发生冲突的概率会大大增加。
具体代码:
typedef unsigned long long ull; const int maxn=40005; ull seed=31,ha[maxn],wei[amxn]; wei[0]=1; for(int i=1;i<maxn;i++) wei[i]=wei[i-1]*seed;//对应长度字符串的权 ha[len]=0; for(int i=len-1;i>=0;i--) ha[i]=ha[i+1]*seed+str[i]-'a'; //求长度为l的字符串哈希值 tmp=ha[i]-ha[i+l]*wei[l]; //对字符串hash可以从左到右,也可以从右到左
HDU4821MAP+HASH
#include<cstdio> #include<cstring> #include<algorithm> #include<map> using namespace std; #define N 100010 unsigned long long base=31,nbase[N],hash[N]; int n,len,ans,slen; char str[N]; map<unsigned long long,int> mp; int main() { int i,j; unsigned long long tmp; nbase[0]=1; for(i=1;i<N;i++) nbase[i]=nbase[i-1]*base; while(~scanf("%d%d",&n,&len)) { scanf("%s",str); slen=strlen(str); hash[slen]=0; for(i=slen-1;i>=0;i--) { hash[i]=hash[i+1]*base+str[i]-'a'+1; } ans=0; for(i=0;i<len&&i+n*len<=slen;i++) { mp.clear(); for(j=i;j<i+n*len;j+=len) { tmp=hash[j]-hash[j+len]*nbase[len]; mp[tmp]++; } if(mp.size()==n) ans++; for(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 ",ans); } return 0; }
HDU4080二分+hash
#include <cstdio> #include <cstring> #include <map> using namespace std; typedef unsigned long long uLL ; const int maxn = 40050 ; map<uLL,int>mp; int pos ; const uLL p = 9999997 ; uLL powp[maxn] ; uLL ha[maxn] ; char s[maxn] ; bool check(int l , int n , int m){ bool ok = false ; mp.clear(); for(int i=1; i+l-1<=n; i++) { uLL tmp = ha[i+l-1] - ha[i-1] * powp[l]; if(++mp[tmp]>=m){pos=i;ok=true;} } return ok ; } int main() { powp[0] = 1 ; for(int i=1; i<maxn; i++) powp[i] = powp[i-1] * p ; int m ; while(scanf("%d" ,&m)==1 && m){ scanf("%s" ,s+1) ; int n = strlen(s+1) ; ha[0] = ha[n+1] = 0 ; for(int i=1; i<=n;i++) ha[i] = ha[i-1]*p + s[i] ; //from end to begin ha that's why s+1 int L = 0 , R = n ; while(L<R) { int mid = L + (R-L+1)/2 ; if(check(mid , n ,m)) L = mid ; else R = mid - 1 ; } if(!L) puts("none") ; else printf("%d %d " , L , pos-1) ; } return 0; }