Hdu 1381 Crazy Search[Hash||map]

本文主要是介绍Hdu 1381 Crazy Search[Hash||map]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点击打开链接

Hash。hash函数为H（n，nc）=长度为n的子串，化为以nc进制的数。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;const int N=16000005;
int n,nc,p[30];
bool hash[N];
char txt[N];
int main(){int T;scanf("%d",&T);while(T--){memset(hash,0,sizeof(hash));scanf("%d%d%s",&n,&nc,txt);int len=strlen(txt);int ans=len-n+1,k=1,i=0;while(i<len){//这段代码的意思是什么？if(!p[txt[i]-'a'+1]) p[txt[i]-'a'+1]=k++;if(k-1==nc) break;i++;}for(int i=0;i<len-n+1;i++){int sum=0;for(int j=i;j<i+n;j++){sum=sum*nc+p[txt[j]-'a'+1];}sum=sum%N;if(!hash[sum]) hash[sum]=1;else ans--;}printf("%d\n",ans);}return 0;
}

解释代码意思。

while(i<len){//这段代码的意思是什么？if(!p[txt[i]-'a'+1]) p[txt[i]-'a'+1]=k++;if(k-1==nc) break;i++;}//简单来说就是a*b+c*d可能等于e*b+f*d//也就是说,出现的字符可能不是连续的.是离散的.//比如子串aic 和ccc 如果没有该步，那么他们的哈希值是一样的.//所以 该步的作用就是使出现的字符连续.

该题还可以用map来作。很是简单。

#include <iostream>
#include <map>
#include <string>
#include <cstring>
using namespace std;int main(){int T;cin>>T;while(T--){map<string,int> m;string s;int N,NC;cin>>N>>NC>>s;int i,len=s.size();for(i=0;i<len-N+1;i++){string tmp(s,i,N);if(m[tmp]) m[tmp]=1;}cout<<m.size()<<endl;}return 0;
}

对于这几天的学习。感悟：
Hash函数很博大精深。Hash很博大精深。

这篇关于Hdu 1381 Crazy Search[Hash||map]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---