HDU1075 字典树板子题
题意 ：给出两组字符串 一一映射，给出一种组成的文字，要求映射成另外一种
思路：使用字典树，把映射的另外一个字符存在字典树的单词节点处 例如 abc 123
则把123存在abc节点中的c处即可
同时这里使用的是静态的数组，操作和写起来都更方便，就是要提前判断开的空间，过大过小都会有莫名其妙的错误
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int maxn=5e5+5; 6 const int size=26; 7 struct Trie{ 8 int ch[maxn][size]; 9 char str[maxn][20]; 10 bool isEnd[maxn]; 11 int size; 12 void init(){ 13 size=1; 14 memset(ch,0,sizeof(ch)); 15 memset(isEnd,0,sizeof(isEnd)); 16 } 17 int index(char s){ 18 return s-'a'; 19 } 20 void insert(char*s1,char*s2){ 21 int i,rt; 22 for(i=rt=0;s1[i]!='\0';i++){ 23 int c=index(s1[i]); 24 if(ch[rt][c]==0){ 25 ch[rt][c]=size++; 26 } 27 rt=ch[rt][c]; 28 } 29 strcpy(str[rt],s2); 30 isEnd[rt]=1; 31 } 32 const char*find(char*s){ 33 int i,rt; 34 for(i=rt=0;s[i]!='\0';i++){ 35 int c=index(s[i]); 36 if(!ch[rt][c])return "0"; 37 rt=ch[rt][c]; 38 } 39 return (isEnd[rt])?str[rt]:"0"; 40 41 } 42 }trie; 43 char s1[maxn],s2[maxn]; 44 int main(){ 45 trie.init(); 46 while(scanf("%s",s1)==1){ 47 if(!strcmp(s1,"START"))continue; 48 if(!strcmp(s1,"END"))break; 49 scanf("%s",s2); 50 trie.insert(s2,s1); 51 } 52 //cout<<111<<endl; 53 getchar(); 54 while(gets(s1)){ 55 if(!strcmp(s1,"START"))continue; 56 if(!strcmp(s1,"END"))break; 57 int i=0; 58 while(s1[i]!='\0'){ 59 if(s1[i]>='a'&&s1[i]<='z'){ 60 int j=0; 61 while(s1[i]!='\0'&&s1[i]>='a'&&s1[i]<='z'){ 62 s2[j++]=s1[i++]; 63 } 64 s2[j]='\0'; 65 const char*temp=trie.find(s2); 66 if(temp[0]=='0')printf("%s",s2); 67 else printf("%s",temp); 68 } 69 else putchar(s1[i++]); 70 // puts(""); 71 } 72 // puts(""); 73 cout<<endl; 74 } 75 return 0; 76 }
