hdu--1075--字典樹||map

做這題的時候我完全沒想到字典樹就直接用map來做了 =-=

我是有多不敏感啊~~

然后去 discuss 一看很多都是說字典樹的問題....

字典樹給我感覺它的各個操作的意思都很清晰明了直接手寫不那么容易啊。。

晚些時候試下來寫------用map寫是真心方便只要注意下那么\n的吸收之類的? 但是速度上是的確慢了許多基本要卡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] = '\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] = '\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] = '\0';
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] = '\0';
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] = '\0';
123                 cout << find(str4);
124             }
125         }
126         cout << endl;
127     }
128     return 0;
129 }

View Code

關于字典樹分靜態和動態版本我還是個人傾向于動態的寫起來方便啊...雖然會內存大點時間慢點一般應該是能過的吧

today:

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

　　　　　　　　　　------希望如愿

轉載于:https://www.cnblogs.com/radical/p/3887096.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/260175.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/260175.shtml
英文地址，請注明出處：http://en.pswp.cn/news/260175.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！