这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1075
这题用字典树Trie做很麻烦,用STL map要简单多了。
字典树的讲解;
http://www.wutianqi.com/?p=1359
我用字典树做了一个:
// Author: Tanky Woo
// www.wutianqi.com
// HDOJ 1075
// Trie
#include
using namespace std;
typedef struct Trie{
//int v;
Trie *next[26];
char english[20];
}Trie;
Trie root;
void createTrie(char *eng, char *mar)
{
int len = strlen(mar);
Trie *p = &root;, *q;
for(int i=0; inext[id] == NULL)
{
q = (Trie *)malloc(sizeof(root));
for(int j=0; j<26; ++j)
q->next[j] = NULL;
strcpy(q->english, "");
p->next[id] = q;
p = p->next[id];
}
else
{
p = p->next[id];
}
}
strcpy(p->english, eng);
}
char* findTrie(char *str)
{
int len = strlen(str);
Trie *p = &root;
int i;
for(i=0; inext[id];
if(p == NULL)
break;
}
if(str[i] == 0 && strcmp(p->english, "")!=0)
return p->english;
return 0;
}
int main()
{
freopen("input.txt", "r", stdin);
char s1[15], s2[15], laji[15];
int i;
scanf("%s", laji); // "START"
while(scanf("%s", s1) && strcmp(s1, "END")!=0)
{
scanf("%s", s2);
createTrie(s1, s2);
}
scanf("%s", laji); // "START"
getchar();
char str[1000];
while(gets(str) && strcmp(str, "END")!=0)
{
int len = strlen(str);
str[len] = ' ';
str[++len] = 0;
char ss[1000];
int k = 0;
for(i=0; i='a' && str[i]<='z'))
{
ss[k] = 0;
char *t = findTrie(ss);
if(t)
printf("%s", t);
else
printf("%s", ss);
k = 0;
if(i != len-1)
printf("%c", str[i]);
}
else
{
ss[k++] = str[i];
}
}
printf("\n");
}
return 0;
}
这个是网上一位朋友的代码,分别是用字典树和map做的:
// 字典树
#include
#include
using namespace std;
int i;
struct dictree
{
dictree *child[26];
char engWord[11];
dictree()//初始化非常的有必要
{
for(i=0;i<26;i++)
child[i] = NULL;
engWord[0]='\0';
}
};
dictree root;
void insert(char eng[],char mar[])//构建字典树
{
dictree *now = &root;
char *tmp = mar;
while(*tmp)
{
if(now->child[*tmp-'a']==NULL)
now->child[*tmp-'a'] = new dictree;
now = now->child[*tmp-'a'];
tmp++;
}
strcpy(now->engWord,eng);
}
char *find(char ch[])//查找单词
{
dictree *p = &root;
int k=0;
while(1)
{
if(ch[k]=='\0' || p->child[ch[k]-'a']==NULL)
break;
p = p->child[ch[k]-'a'];
k++;
}
if(ch[k]=='\0' && strcmp(p->engWord,"")!=0)
return p->engWord;
return NULL;
}
int main()
{
char a[11],b[11];
scanf("%s",a);//"START"
while(scanf("%s",a) && strcmp(a,"END")!=0 )
{
scanf("%s",b);
insert(a,b);
}
scanf("%s",a);//"START"
getchar();//吃回车
char tmp[3002];
while(1)
{
gets(tmp);//用这个比getline()强
if(strcmp(tmp,"END") == 0 )
break;
int i,len,k=0;
len = strlen(tmp);
tmp[len]=' ';//多加一个' ',输出的时候注意
tmp[++len]='\0';
char tp[3002];
for(i=0;i='a' && tmp[i]<='z'))//非小写字母
{
tp[k]='\0';
char *temp = find(tp);//查找是否有对应的engWord
if(temp)//存在这个单词
printf("%s",temp);
else
printf("%s",tp);//可以用cout<
#include
#include
using namespace std;
mapM;
int main()
{
string a,b;
cin>>a;//"START"
while(cin>>a && a!="END")
{
cin>>b;
M[b] = a;
}
cin>>a;//"START"
getchar();//吃回车
char tmp[3005];
while(1)
{
gets(tmp);//用这个比getline()强
if(strcmp(tmp,"END") == 0 )
break;
int i,len;
len = strlen(tmp);
b = "";
for(i=0;i='a' && tmp[i]<='z'))//非小写字母
{
if(M[b]!="")//存在这个单词
cout<<M[b];
else
cout<<b;
b="";
cout<<tmp[i];
}
else //小写字母
b+=tmp[i];
}
cout<<endl;
}
return 0;
}