HDU-1075-What Are You Talking About
http://acm.hdu.edu.cn/showproblem.php?pid=1075
字典树
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct node
{
int count;
node *childs[26];
char tran[15];
node()
{
count=0;
for(int i=0;i<26;i++)
childs[i]=NULL;
memset(tran,0,sizeof(tran));
}
};
node *root,*current,*newnode;
void insert(char *str,char *s)
{
int i,m;
current=root;
for(i=0;i<strlen(str);i++)
{
m=str[i]-'a';
if(current->childs[m]!=NULL)
current=current->childs[m];
else
{
newnode=new node;
current->childs[m]=newnode;
current=newnode;
}
}
current->count=1;
strcpy(current->tran,s);
}
string search(string str)
{
int i,m,flag;
current=root;
flag=1;
for(i=0;i<str.length();i++)
{
m=str[i]-'a';
if(current->childs[m]==NULL)
{
flag=0;
break;
}
current=current->childs[m];
}
if(flag&&i==str.length()&¤t->count==1)
return current->tran;
return str;
}
int main()
{
int i,len;
char st[15],ed[15];
char ss[3005];
string word,ans;
root=new node;
scanf("%s",st);
while(scanf("%s",st),strcmp(st,"END"))
{
scanf("%s",ed);
insert(ed,st);
}
scanf("%s",st);
getchar();
while(gets(ss),strcmp(ss,"END"))
{
len=strlen(ss);
ans="";
word="";
for(i=0;i<len;i++)
{
if(ss[i]>='a'&&ss[i]<='z')
word+=ss[i];
else
{
ans+=search(word);
word="";
ans+=ss[i];
}
}
printf("%s\n",ans.c_str());
}
return 0;
}
分享到:
相关推荐
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
算法-数塔(HDU-2084).rar
算术(HDU-6715).rar
算法-确定比赛名次(HDU-1285).rar
最短路(HDU-2544).rar
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
算法-命运(HDU-2571)(包含源程序).rar
算法-连连看(HDU-1175)(包含源程序).rar
算法-欧拉回路(HDU-1878)(包含源程序).rar
算法-迷宫城堡(HDU-1269)(包含源程序).rar
算法-免费馅饼(HDU-1176)(包含源程序).rar
算法-六度分离(HDU-1869)(包含源程序).rar