hdu 1075 What Are You Talking About (字典树)
题目大意: 类似解密过程,右边是单词对应的密文 给出一串字符,可以解密的单词都翻译出来
解题思路: 将明文存进数组,然后将密文建成Trie树
将最后结点存进树时顺便记录它明文的下标
搜索密文的每一个单词,若在树中则翻译出来
代码:
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100000 struct snode{ int next[27]; //第一种写法 int w; }Tree[MAX*10]; char ch1[MAX*11][11],ch2[11]; int Index; void Insert(int k,int Tlen) //遍历插入字典树 { int i,S=0,child; for(i=1;i<=Tlen;i++) { child=ch2[i-1]-'a'+1; if(Tree[S].next[child]==0) { if(i==Tlen) Tree[Index].w=k; Tree[S].next[child]=Index++; } else { if(i==Tlen) Tree[Tree[S].next[child]].w=k; } S=Tree[S].next[child]; } } int Query(char ch5[],int Tlen) //遍历查询字典树 { int i,S=0,child; for(i=1;i<=Tlen;i++) { child=ch5[i-1]-'a'+1; if(Tree[S].next[child]!=0) { if(i==Tlen&&Tree[Tree[S].next[child]].w!=0) { printf("%s",ch1[Tree[Tree[S].next[child]].w]); return 1; } S=Tree[S].next[child]; } else return 0; } return 0; } int main() { int n=1,i,j; char ch3[10000],ch4[20]; Index=1; memset(Tree,0,sizeof(Tree)); scanf("%s",ch3); while(scanf("%s",ch1[n])) { if(strcmp(ch1[n],"END")==0) break; scanf("%s",ch2); Insert(n,strlen(ch2)); n++; } scanf("%s",ch3); getchar(); while(gets(ch3)) { if(strcmp(ch3,"END")==0) { break; } for(i=0,j=0;ch3[i]!='\0';i++) { if(ch3[i]<'a'||ch3[i]>'z') //枚举每个单词是否存在翻译 { if(Query(ch4,j)==0) { printf("%s",ch4); } printf("%c",ch3[i]); ch4[0]='\0'; //不存在初始化继续枚举下一个 j=0; } else { ch4[j++]=ch3[i]; ch4[j]='\0'; } } if(ch4[0]!='\0') //***最后一个单词 { if(Query(ch4,j)==0) printf("%s",ch4); } puts(""); } return 0; }
补充:软件开发 , C++ ,