算法笔记：字符串哈希初步

问题描述： 给出N个字符串，每个字符串由三位大写字母组成，再给出M个查询字符串，问每个查询字符串在N个字符串中出现的次数？ 解题思路： 把字符串转化为整数，利用空间来换时间效率。

C/C++代码：

#include<cstdio> #include<cstring> const int maxn=100; char S[maxn][5],temp[5]; int Hashtable[26*26*26+10]={0}; // 哈希函数，把字符串映射为整数，从而可以作为数组下标 int hashFun(char S[],int len) { int id=0; for(int i=0;i<len;i++) { id=id*26+(S[i]-'A'); } return id; } int main(){ int n,m; scanf("%d %d",&n,&m); for(int i=0;i<n;i++) { scanf("%s",S[i]); int id=hashFun(S[i],strlen(S[i])); Hashtable[id]++; } for(int i=0;i<m;i++) { scanf("%s",temp); int id=hashFun(temp,strlen(S[i])); printf("%d\n",Hashtable[id]); } return 0; }