字符串哈希 - HDU - 1880 询问字符串是否存在 哈希+map
程序员文章站
2024-03-17 08:43:22
...
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1880
题目大意:
[ ]中的为魔咒, 右边为功能。
询问:
询问是魔咒,输出功能
询问是功能,输出魔咒
直接哈希+map
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define LL long long
const int maxn=1000010;
ull base =131;
ull g[maxn];
map<ull , char *> mp;
char T[200];
ull Hash(char s[])
{
int len=strlen(s);
ull ans=0;
g[0]=s[0];
for(int i=1;i<len;i++)
{
g[i]=g[i-1]*base+s[i];
}
return g[len-1];
}
int main()
{
while(1)
{
fgets(T,200,stdin);
if(T[0]=='@')
{
break;
}
int n=strlen(T), k=1, cut=0;
char s[25]={0}, t[85]={0};
for(int i=1;i<n-1;i++)
{
if(T[i]==']')
{
i++;
k=2;
continue;
}
if(k==1)
{
s[i-1]=T[i];
}
if(k==2)
{
t[cut++]=T[i];
}
}
char *p1=new char [25];
char *p2=new char [85];
strcpy(p1, s);
strcpy(p2, t);
mp[Hash(s)]= p2, mp[Hash(t)]= p1;
}
int n;
scanf("%d%*c",&n);
while(n--)
{
fgets(T,200,stdin);
char s[200]={0};
int len=strlen(T), cut=0;
for(int i=0;i<len-1;i++)
{
if(T[i]!='['&&T[i]!=']')
{
s[cut++]=T[i];
}
}
ull k=Hash(s);
if(mp[k]!=0)
{
printf("%s\n",mp[k]);
}
else
{
printf("what?\n");
}
}
return 0;
}