题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1075
题意：比较简单，易懂，这里不做说明。
解法：第一种方法：用map映射，耗时1000+ms；第二种方法：用字典树处理，500+ms。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#define inf 0x7fffffff
using namespace std;
char s1[],s2[];
typedef struct NODE
{
NODE *child[];
char str[];
int ok;
NODE () {ok= ;str[]= ;for (int i= ;i< ;i++) child[i]=NULL; } }node;
void insert(node *root)
{
node *cur=root;
int len=strlen(s2);
int k;
for (int i= ;i<len ;i++)
{
k=s2[i]-'a';
if (cur->child[k]!=NULL)
{
cur=cur->child[k];
}else
{
node *q=new node;
q->ok=;
q->str[]=;
for (int i= ;i< ;i++) q->child[i]=NULL;
cur->child[k]=q;
cur=cur->child[k];
}
}
cur->ok=;
strcpy(cur->str,s1);
}
int findTree(node *root)
{
node *cur=root;
int len=strlen(s2);
for (int i= ;i<len ;i++)
{
int k=s2[i]-'a';
cur=cur->child[k];
if (cur==NULL) return ;
}
if (cur->ok == ) {printf("%s",cur->str);return ;}
return ;
}
void del(node *root)
{
for (int i= ;i< ;i++) if (root->child[i]) del(root->child[i]);
delete root;
root=NULL;
}
int main()
{
memset(s1,,sizeof(s1));
memset(s2,,sizeof(s2));
node *root=new node;
cin>>s1;
while (scanf("%s",s1)!=EOF)
{
if (strcmp(s1,"END")==) break;
scanf("%s",s2);
//cout<<s1<<" "<<s2<<endl;
insert(root);
}
cin>>s1;
char s[];
memset(s,,sizeof(s));
getchar();
while (gets(s))
{
//if (s[0]=='E' && s[1]=='N' && s[2]=='D') break;
if (strcmp(s,"END")==) break;
memset(s2,,sizeof(s2));
int cnt=;
int flag=;
int len=strlen(s);
for (int i= ;i<len ;i++)
{
if (s[i]>='a' && s[i]<='z')
{
flag=;
s2[cnt++]=s[i];
}
else if (flag)
{
flag=;
s2[cnt]=;
int m=findTree(root);
if (!m) printf("%s",s2);
cnt=;
memset(s2,,sizeof(s2));
}
if (!flag) printf("%c",s[i]);
}
if (flag)
{
s2[cnt]=;
int m=findTree(root);
if (!m) printf("%s",s2);
}
cout<<endl;
}
del(root);
//system("pause");
return ;
}