STL之map应用 +hash表(51nod 1095)

题目:Anigram单词

题意:给出词典,再给出一些单词,求单词的Anigram数量。

思路:先将字串转换成哈希表,然后再用map链接。

hash表构造方法汇总:http://www.cnblogs.com/gj-Acit/archive/2013/05/06/3062628.html

此题使用除留余数法。

#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map> #define c_false ios_base::sync_with_stdio(false); cin.tie(0)
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define zero_(x,y) memset(x , y , sizeof(x))
#define zero(x) memset(x , 0 , sizeof(x))
#define MAX(x) memset(x , 0x3f ,sizeof(x))
#define swa(x,y) {LL s;s=x;x=y;y=s;}
using namespace std;
#define N 10005
const int MOD = 1e7+;
const int base = ; const double PI = acos(-1.0);
typedef long long LL ; map <string, int> MAP;
int has[MOD+], cnt[base+];
char s[];
int n,m;
int Hash(){
zero(cnt);
for(int i = ; s[i] ;i++){
if(s[i] >= 'a' && s[i] <= 'z') cnt[s[i] - 'a']++;
else cnt[s[i] - 'A' +]++;
}
int res = ;
for(int i = ; i < base; i++){
res = (res*base + cnt[i])%MOD;
}
return res;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios_base::sync_with_stdio(false); cin.tie(0);
scanf("%d", &n);
while(n--){
scanf("%s", s);
string k = s;
++has[Hash()];
if(MAP[k] ==) MAP[k]++;
}
scanf("%d", &m);
while(m--){
scanf("%s", s);
string k = s;
int num = Hash();
int sum = has[num];
if(MAP[k]>) sum--; ///记得把自己减去;
printf("%d\n",sum);
}
return ;
}
上一篇:work4


下一篇:php Imagick库readImage()报Postscript delegate failed 解决方法(失效)