HDOJ 1075 What Are You Talking About Trie( STL )

原创

转载请注明：www.cnblogs.com/yewei

方法一：Trie

思路：

1. 开辟一个结构体数组dict，数组中存放索引值和索引，比如from fiwo

2. 建立一颗Trie，Trie维护整型变量 index，结构体指针数组 branch，在建立Trie的过程中，若是单词结尾，Trie中index赋值为dict的索引，否则为-1

写法一：string类降低编码复杂度，当然代价是时间复杂度加大约 2 倍

View Code

  1 /*
  2 PROG:   What Are You Talking About
  3 ID  :   yewei
  4 LANG:   C++
  5 */
  6 #include <map>
  7 #include <string>
  8 #include <cstdio>
  9 #include <cstdlib>
 10 #include <cstring>
 11 #include <iostream>
 12 #include <memory.h>
 13 #include <algorithm>
 14 using namespace std;
 15 
 16 struct Dictionary
 17 {
 18     string front, back;
 19 }dict[500004];
 20 
 21 struct Trie_Node
 22 {
 23     int index;
 24     Trie_Node *branch[27];
 25     Trie_Node(): index( -1 )
 26     {
 27         memset( branch, 0, sizeof(branch) );
 28     }
 29 };
 30 class Trie
 31 {
 32     public:
 33         Trie();
 34         ~Trie() { }
 35         void Trie_Insert( int k, string ss );
 36         int Trie_Find( string ss );
 37         
 38     private:
 39         Trie_Node *root;
 40 }t;
 41 
 42 /* Valiable */
 43 int M=0;
 44 
 45 Trie::Trie()
 46 {
 47     root = new Trie_Node();
 48 }// Trie
 49 
 50 void Trie::Trie_Insert( int k, string ss )
 51 {
 52     Trie_Node *ptr = root;
 53     int slen = ss.length();
 54     for ( int i=0; i<slen; ++i )
 55     {
 56         if ( ptr->branch[ ss[i]-'a' ]==NULL )
 57         {
 58             Trie_Node *temp = new Trie_Node();
 59             ptr->branch[ ss[i]-'a' ] = temp;
 60         }
 61     
 62         ptr = ptr->branch[ ss[i]-'a' ];
 63     }
 64     
 65     ptr->index = k;
 66 }// Trie_Insert
 67 
 68 int Trie::Trie_Find( string ss )
 69 {
 70     Trie_Node *ptr = root;
 71     int slen = ss.length();
 72     for ( int i=0; i<slen; ++i )
 73     {
 74         if ( ptr->branch[ ss[i]-'a' ]!=NULL )
 75             ptr = ptr->branch[ ss[i]-'a' ];
 76         else
 77             return -1;
 78     }
 79     
 80     return ptr->index;
 81 }// Trie_Find
 82 
 83 void ReadData()
 84 {
 85     string s1, s2;
 86     
 87     cin >> s1;   // Words " START "
 88     while ( cin >> s1 && s1!="END" )
 89     {
 90         cin >> s2;
 91         dict[M].front = s1;
 92         dict[M].back = s2;
 93         
 94         t.Trie_Insert( M++, s2 );   // Note " M++ "
 95     }// dictionary
 96 }// ReadData
 97 
 98 void Solve()
 99 {
100     int  slen, kk;
101     string words, line;
102     
103     cin >> line;  // Words " START "
104     getchar();
105     while ( getline( cin, line ) && line!="END" )
106     {
107         words = "";
108         slen = line.length();
109         for ( int i=0; i<slen; ++i )
110         {
111             if ( isalpha( line[i] ) )
112             {
113                 words += line[i];
114             }
115             else
116             {
117                 kk = t.Trie_Find( words );
118                 if ( kk==-1 )
119                     cout << words;
120                 else
121                     cout << dict[kk].front;
122                 cout << line[i];
123                 
124                 words = "";
125             }
126         }// scanning
127         
128         cout << endl;
129     }// books
130 }// Solve
131 
132 int main()
133 {
134     ReadData();
135     Solve();
136     
137     return 0;
138 }

写法二：C语言的写法，编码复杂度加大，时间复杂度尚可，250MS

View Code

  1 /*
  2 PROG:   What Are You Talking About
  3 ID  :   ouyangyewei
  4 LANG:   C++
  5 */
  6 #include <map>
  7 #include <string>
  8 #include <cstdio>
  9 #include <cstdlib>
 10 #include <cstring>
 11 #include <iostream>
 12 #include <memory.h>
 13 #include <algorithm>
 14 using namespace std;
 15 
 16 const int maxn = 15;
 17 
 18 struct Dictionary
 19 {
 20     char front[maxn];
 21     char back[maxn];
 22 }dict[500004]; 
 23 
 24 struct Trie_Node
 25 {
 26     int index;
 27     Trie_Node *branch[27];
 28     Trie_Node(): index( -1 )
 29     {
 30         memset( branch, 0, sizeof(branch) );
 31     }
 32 };
 33 class Trie
 34 {
 35     public:
 36         Trie();
 37         ~Trie() { }
 38         void Trie_Insert( int k, char ss[] );
 39         int Trie_Find( char ss[] );
 40         
 41     private:
 42         Trie_Node *root;
 43 }t;
 44 
 45 /* Valiable */
 46 int M=0;
 47 
 48 Trie::Trie()
 49 {
 50     root = new Trie_Node();
 51 }// Trie
 52 
 53 void Trie::Trie_Insert( int k, char ss[] )
 54 {
 55     Trie_Node *ptr = root;
 56     int slen = strlen( ss );
 57     for ( int i=0; i<slen; ++i )
 58     {
 59         if ( ptr->branch[ ss[i]-'a' ]==NULL )
 60         {
 61             Trie_Node *temp = new Trie_Node();
 62             ptr->branch[ ss[i]-'a' ] = temp;
 63         }
 64     
 65         ptr = ptr->branch[ ss[i]-'a' ];
 66     }
 67     
 68     ptr->index = k;
 69 }// Trie_Insert
 70 
 71 int Trie::Trie_Find( char ss[] )
 72 {
 73     Trie_Node *ptr = root;
 74     int slen = strlen( ss );
 75     for ( int i=0; i<slen; ++i )
 76     {
 77         if ( ptr->branch[ ss[i]-'a' ]!=NULL )
 78             ptr = ptr->branch[ ss[i]-'a' ];
 79         else
 80             return -1;
 81     }
 82     
 83     return ptr->index;
 84 }// Trie_Find
 85 
 86 void ReadData()
 87 {
 88     char s1[maxn], s2[maxn];
 89     
 90     scanf("%s", &s1);   // Words " START "
 91     while ( EOF!=scanf("%s", s1), strcmp(s1, "END")!=0 )
 92     {
 93         scanf("%s", &s2);
 94         strcpy( dict[M].front, s1 );
 95         strcpy( dict[M].back, s2 );
 96         
 97         t.Trie_Insert( M++, s2 );   // Note " M++ "
 98     }// dictionary
 99 }// ReadData
100 
101 void Solve()
102 {
103     int  slen, tlen, kk;
104     char words[maxn], line[3004];
105     
106     scanf("%s", line);  // Words " START "
107     getchar();
108     while ( gets( line ), strcmp( line, "END" )!=0 )
109     {
110         tlen = 0;
111         slen = strlen( line );
112         memset( words, 0, sizeof(words) );
113         
114         for ( int i=0; i<slen; ++i )
115         {
116             if ( isalpha( line[i] ) )
117             {
118                 words[ tlen++ ] = line[i];
119             }
120             else
121             {
122                 kk = t.Trie_Find( words );
123                 if ( kk==-1 )
124                     printf("%s", words);
125                 else
126                     printf("%s", dict[kk].front);
127                 printf("%c", line[i]);
128                 
129                 tlen = 0;
130                 memset( words, 0, sizeof(words) );
131             }
132         }// scanning
133         
134         printf("\n");
135     }// books
136 }// Solve
137 
138 int main()
139 {
140     ReadData();
141     Solve();
142     
143     return 0;
144 }

方法二：STL MAP

编码复杂度低，时间复杂度差

View Code

 1 /*
 2 PROG:   What Are You Talking About
 3 ID  :   ouyangyewei
 4 LANG:   C++
 5 */
 6 #include <map>
 7 #include <string>
 8 #include <cstdio>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <iostream>
12 #include <memory.h>
13 #include <algorithm>
14 using namespace std;
15 
16 int slen;
17 string s1, s2, line, result;
18 map <string, string> data;
19 
20 int main()
21 {    
22     cin >> s1;   // START
23     while ( cin >> s1, s1!="END" )
24     {
25         cin >> s2;
26         data[ s2 ] = s1;
27     }// dictionary
28     
29     cin >> s1;
30     getchar();  // fetch carry reture
31     while ( getline( cin, line ) && line!="END" )
32     {
33         result = "";
34         slen = line.length();
35         for ( int i=0; i<slen; ++i )
36         {
37             if ( isalpha( line[i] ) )
38             {
39                 result += line[i];
40             }
41             else
42             {
43                 if ( data[ result ]=="" )
44                     cout << result;
45                 else
46                     cout << data[ result ];
47                 cout << line[i];
48                 
49                 result = "";
50             }
51         }// scanning
52         
53         cout << endl;
54     }// books
55     
56     return 0;
57 }