欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

字符串哈希 - HDU - 1880 询问字符串是否存在 哈希+map

程序员文章站 2024-03-17 08:43:22
...

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1880
题目大意:
[ ]中的为魔咒, 右边为功能。
询问:
询问是魔咒,输出功能
询问是功能,输出魔咒

直接哈希+map
字符串哈希 - HDU - 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;
}