213
uva 10887 - Concatenation of Languages
注意有空串，题目没有说
用cin会超时，手写hash过的，用了经典的ELFhash，但貌似故意卡了这种hash，要解决冲突。
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define Maxn 9999991
using namespace std;
int first[10000000];
char s[1505*1505][30];
int next[1505*1505];
int na,nb,ans;
char a[1505][11],b[11],tt[21];
int ELFhash(char *str)
{
long long int hash=0,x=0;
while(*str)
{
hash=(hash<<4)+(*str++);
if((x=hash&0xF0000000L)!=0)
{
hash^=(x>>24);
hash&=~x;
}
}
return (hash&0x7FFFFFFFL)%Maxn;
}
bool insert(char *str,int now)
{
int i;
if(!first[now])
{
first[now]=ans;
return 1;
}
for(i=first[now];next[i]!=-1;i=next[i])
{
if(strcmp(s[i],str)==0)return 0;
}
if(strcmp(s[i],str)==0)return 0;
next[i]=ans;
return 1;
}
int main()
{
int T,i,j,C=0;
scanf("%d",&T);
while(T--)
{
C++;
memset(first,0,sizeof(first));
memset(next,-1,sizeof(next));
scanf("%d%d",&na,&nb);
getchar();
for(i=0;i<na;i++)
gets(a[i]);
int t;
ans=1;
for(j=0;j<nb;j++)
{
gets(b);
for(i=0;i<na;i++)
{
strcpy(tt,a[i]);
strcat(tt,b);
strcpy(s[ans],tt);
t=ELFhash(tt);
if(insert(tt,t))
ans++;
}
}
cout<<"Case "<<C<<": "<<ans-1<<endl;
}
}
最后更新：2017-04-04 07:03:41