hdu--1075--字典树||map

做这题的时候我完全没想到字典树就直接用map来做了 =-=

我是有多不敏感啊~~

然后去 discuss 一看很多都是说字典树的问题....

字典树给我感觉它的各个操作的意思都很清晰明了直接手写不那么容易啊。。

晚些时候试下来写------用map写是真心方便只要注意下那么的吸收之类的但是速度上是的确慢了许多基本要卡1000ms 虽然这题是给了5000ms 怎么给那么大的时间

　　　　touch me

 1 #include <iostream>
 2 #include <map>
 3 #include <string>
 4 using namespace std;
 5 
 6 map<string,string>mp;
 7 string str;
 8 string str1;
 9 string str2;
10 string sen;
11 
12 int main()
13 {
14     cin.sync_with_stdio(false);
15     mp.clear();
16     cin >> str;// start
17     while( cin>>str1 && str1!="END" )
18     {
19         cin >> str2;
20         mp[str2] = str1;
21     }
22     getchar();
23     getline(cin,str);// start
24     while( getline(cin,str1) && str1!="END" )
25     {
26         sen = "";
27         int len = str1.length();
28         for( int i = 0 ; i<len ; i++ )
29         {
30             if( str1[i]>='a' && str1[i]<='z' )
31             {
32                 sen += str1[i];
33             }
34             else
35             {
36                 if( sen!="")
37                 {
38                     if( mp.find(sen)!=mp.end() )
39                         cout << mp[sen];
40                     else
41                         cout << sen;
42                 }
43                 cout << str1[i];
44                 sen = "";
45             }
46             if( i==len-1 && (str1[i]>='a'&&str1[i]<='z') )
47             {
48                 if( sen!="" )
49                 {
50                     if( mp.find(sen)!=mp.end() )
51                         cout << mp[sen];
52                     else
53                         cout << sen;
54                 }
55             }
56         }
57         cout << endl;
58     }
59     return 0;
60 }

View Code

--------实在懒得敲代码...昨天的搁到今天刚刚才写好

  1 #include <iostream>
  2 #include <cstring>
  3 using namespace std;
  4 
  5 const int size = 26;
  6 const int num = 15;
  7 char str[num];
  8 char str1[3010];
  9 char str2[num];
 10 char str3[num];
 11 char str4[num];
 12 typedef struct trie
 13 {
 14     trie* next[size];
 15     char ans[num];
 16 };
 17 trie root;
 18 
 19 void init( )
 20 {
 21     root.ans[0] = '';
 22     for( int i = 0 ; i<size ; i++ )
 23     {
 24         root.next[i] = NULL;
 25     }
 26 }
 27 
 28 void create( char* str1 , char* str2 )
 29 {
 30     int len = strlen(str1);
 31     trie* p = &root;
 32     trie* q;
 33     for( int i = 0 ; i<len ; i++ )
 34     {
 35         int id = str1[i] - 'a';
 36         if( p->next[id] == NULL )
 37         {
 38             q = new trie;
 39             q->ans[0] = '';
 40             for( int i = 0 ; i<size ; i++ )
 41             {
 42                 q->next[i] = NULL;
 43             }
 44             p->next[id] = q;
 45         }
 46         p = p->next[id];
 47     }
 48     strcpy( p->ans , str2 );
 49 }
 50 
 51 char* find( char* str )
 52 {
 53     int len = strlen(str);
 54     trie* p = &root;
 55     for( int i = 0 ; i<len ; i++ )
 56     {
 57         int id = str[i] - 'a';
 58         if( p->next[id] == NULL )
 59             return str;
 60         p = p->next[id];
 61     }
 62     if( strlen(p->ans) )
 63         return p->ans;
 64     else
 65         return str;
 66 }
 67 
 68 void dealTrie( trie* T )
 69 {
 70     if( T == NULL )
 71     {
 72         return;
 73     }
 74     for( int i = 0; i<size ; i++ )
 75     {
 76         if( T->next[i] != NULL )
 77         {
 78             dealTrie( T->next[i] );
 79         }
 80     }
 81     delete T;
 82     return;
 83 }
 84 
 85 int main()
 86 {
 87     int cnt , len;
 88     init();
 89     scanf( "%s",str );
 90     while( scanf( "%s",str1) && strcmp(str1,"END") )
 91     {
 92         scanf( "%s",str2 );
 93         create( str2 , str1 );
 94     }
 95     scanf( "%s",str );
 96     getchar();
 97     while( gets(str1) )
 98     {
 99         if( !strcmp(str1,"END") )
100         {
101             dealTrie(&root);
102             break;
103         }
104         cnt = 0;
105         str4[cnt] = '';
106         len = strlen(str1);
107         for( int i = 0 ; i<len ; i++ )
108         {
109             if( str1[i]>='a' && str1[i]<='z' )
110             {
111                 str4[cnt++] = str1[i];
112             }
113             else
114             {
115                 str4[cnt] = '';
116                 cout << find(str4);
117                 cnt = 0;
118                 printf( "%c",str1[i] );
119             }
120             if( i==len-1 && ( str1[i]>='a' && str1[i]<='z' ) )
121             {
122                 str4[cnt] = '';
123                 cout << find(str4);
124             }
125         }
126         cout << endl;
127     }
128     return 0;
129 }

View Code

关于字典树分静态和动态版本我还是个人倾向于动态的写起来方便啊...虽然会内存大点时间慢点一般应该是能过的吧

today:

　　祝天下有情人皆是失散多年的兄妹

　　　　　　　　　　------希望如愿

just follow your heart