hdu 1880 字符串hash

时间:2022-04-06 08:44:44
/*普通的hsah 由于元素太多 空间很小..hash碰撞很厉害.30分*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define maxn 100010
#define mod 2000007
#define hs 117
using namespace std;
int n,l,k,cnt,f[mod+],l1[maxn],l2[maxn];
char s[],c,s1[maxn][],s2[maxn][];
int main()
{
while()
{
gets(s);if(s[]=='@')break;
cnt++;l=strlen(s);
for(int i=;i<l;i++)
{
if(s[i]=='[')continue;
if(s[i]==']'){k=i+;break;}
s1[cnt][++l1[cnt]]=s[i];
}
for(int i=k;i<l;i++)s2[cnt][++l2[cnt]]=s[i];
int a1=,a2=;
for(int i=;i<=l1[cnt];i++)
a1=a1*s1[cnt][i]*mod+s1[cnt][i]*i;
if(a1<)a1=-a1;a1=a1%mod;
for(int i=;i<=l2[cnt];i++)
a2=a2*s2[cnt][i]*mod+s2[cnt][i]*i;
if(a2<)a2=-a2;a2=a2%mod;
f[a1]=cnt;f[a2]=cnt;
}
cin>>n;c=getchar();
for(int i=;i<=n;i++)
{
gets(s);l=strlen(s);int li=,falg=;
char si[];memset(si,,sizeof(si));
for(int i=;i<l;i++)
{
if(s[i]=='['){falg=;continue;}
if(s[i]==']')break;
si[++li]=s[i];
}
int ai;if(falg)ai=;else ai=;
for(int i=;i<=li;i++)
ai=ai*si[i]*mod+si[i]*i;
if(ai<)ai=-ai;ai=ai%mod;
if(f[ai]==)printf("what?\n");
else
{
if(falg)
{
for(int i=;i<=l2[f[ai]];i++)
printf("%c",s2[f[ai]][i]);
printf("\n");
}
else
{
for(int i=;i<=l1[f[ai]];i++)
printf("%c",s1[f[ai]][i]);
printf("\n");
}
}
}
return ;
}
/*map 爆空间.*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
map<string,string>f;
int n,l,k;
char s[],c;
int main()
{
while()
{
gets(s);
if(s[]=='@')break;
string s1,s2;l=strlen(s);
for(int i=;i<l;i++)
{
if(s[i]=='[')continue;
if(s[i]==']'){k=i+;break;}
s1+=s[i];
}
for(int i=k;i<l;i++)s2+=s[i];
f[s1]=s2;f[s2]=s1;
}
cin>>n;c=getchar();
for(int i=;i<=n;i++)
{
gets(s);
string s1,s2;l=strlen(s);
for(int i=;i<l;i++)
{
if(s[i]=='[')continue;
if(s[i]==']')break;
s1+=s[i];
}
if(f[s1]=="")cout<<"what?"<<endl;
else cout<<f[s1]<<endl;
}
return ;
}

 
/*我同桌的暴力 居然过了....*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100010
using namespace std;
string ss,sss;
char s[];
char s1[maxn][],s2[maxn][];
int n,tot,l1[maxn],l2[maxn];
int main()
{
int i,j,k;
while()
{
gets(s);
if(s[]=='@')break;
tot++;
int l=strlen(s);
for(i=;i<=l-;i++)
{
s1[tot][l1[tot]++]=s[i];
if(s[i]==']')break;
}
for(j=i+;j<=l-;j++)
s2[tot][l2[tot]++]=s[j];
}
cin>>n;
char c=getchar();
while(n--)
{
gets(s);
int l=strlen(s);
ss=s;
if(ss[]=='[')
{
for(i=;i<=tot;i++)
{
sss=s1[i];
if(ss==sss)
{
cout<<s2[i]<<endl;
break;
}
}
if(i==tot+)
cout<<"what?"<<endl;
}
else
{
for(i=;i<=tot;i++)
{
sss=s2[i];
if(ss==sss)
{
for(j=;j<l1[i]-;j++)
cout<<s1[i][j];
cout<<endl;
break;
}
}
if(i==tot+)
cout<<"what?"<<endl;
}
}
return ;
}
/*
后来xzc说类似边表的搞一搞就好了
建一个图 hash值是点的编号 每个字符串是边
每个hash可能对应好几个字符串 都连到这个hash值上
然后查询的时候遍历这个点连出去的所有边
空间有点紧.
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#define maxn 100010
#define mod 100007
#define hs 117
using namespace std;
struct node
{
char s1[],s2[];
int pre;
}A[maxn],B[maxn];
int n,l,k,ha,cnt,heada[mod],headb[mod];
char s[],c,q1[],q2[],si[];
int Hash(char *a)
{
int ret=,l=strlen(a);
for(int i=;i<l;i++)
ret=(ret*hs%mod+a[i])%mod;
return ret%mod;
}
void Insert(char *a,char *b)
{
cnt++;
strcpy(A[cnt].s1,a);
strcpy(A[cnt].s2,b);
ha=Hash(a);
A[cnt].pre=heada[ha];
heada[ha]=cnt;
strcpy(B[cnt].s1,a);
strcpy(B[cnt].s2,b);
ha=Hash(b);
B[cnt].pre=headb[ha];
headb[ha]=cnt;
}
int find1(char *a)
{
ha=Hash(a);
for(int i=heada[ha];i;i=A[i].pre)
if(!strcmp(A[i].s1,a))return i;
return ;
}
int find2(char *a)
{
ha=Hash(a);
for(int i=headb[ha];i;i=B[i].pre)
if(!strcmp(B[i].s2,a))return i;
return ;
}
int main()
{
while()
{
memset(q1,,sizeof(q1));
memset(q2,,sizeof(q2));
gets(s);if(s[]=='@')break;
l=strlen(s);
int l1=-,l2=-;
for(int i=;i<l;i++)
{
if(s[i]=='[')continue;
if(s[i]==']'){k=i+;break;}
q1[++l1]=s[i];
}
for(int i=k;i<l;i++)q2[++l2]=s[i];
Insert(q1,q2);
}
cin>>n;c=getchar();
for(int i=;i<=n;i++)
{
gets(s);l=strlen(s);int li=-,falg=;
for(int i=;i<l;i++)
{
if(s[i]=='['){falg=;continue;}
if(s[i]==']')break;
si[++li]=s[i];
}
if(falg)
{
int r=find1(si);
!r?cout<<"what?"<<endl:cout<<A[r].s2<<endl;
}
else
{
int r=find2(si);
!r?cout<<"what?"<<endl:cout<<B[r].s1<<endl;
}
}
return ;
}