Configuration files
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
In daily project development process, we often use to the configuration file. Now we are going to solve the problem is simple. It is a complete configuration files writing and reading operation and output operation results.
Input
The input contains multiple test cases.The first line has one integer N (1 <= N<= 100), represent the number of the test cases.The second line has one integer M (1 <= M <= 2600) ,represent configuration files contain the M line data. The following next M line data represent the content of configuration files. The next line has one integer K (1 <= K <= 10000), represent the number of the operations. Then next K lines follow, each line represent a operation.there are two format in the operations. The first format is “op nodeName variable Name value “ . The second format is “op nodeName variableName”. If op is “U” that represent that it is the Update operation. If op is “G” that represent that it is the Get operation. If op is “I” that represent that it is the Insert operation. The node’s format in the configuration is “[nodeName]”. The format of the value is “variableName=value”. The nodeName, variableName in the configuration files all consist of lowercase character and each of them most contain 100 characters(include 100). The value consist of printable characters and most contain 100 characters(include 100) There may have some whitespaces (space or Tab key) front or behind the nodeName, variableName and value. There may have multiple same variables in the same node in the configuration file and the value of the variable to last shall prevail and the variable names and node name may be the same, in a configuration file won't exist in the same node name, inserting operations if a specified node name designated variables are the already existing failured.
Output
For each case, firstly print the “case n:” n represent the number of the case.Then operate according to the output corresponding operation results, to “U” operation if successfully output “update succeed.” otherwise output “update failured.”,to “I” operation if successful ouput “insert succeed.” otherwise ouput “insert failured.” for “G” operation if successful output a specified node specified under the value of the variable, or output “not get the value.”.
Sample Input
1
10
[appinfo]
appid = 32152
post = 86,87,89
[userinfo]
name = acmer
password = 2536LR
[softversion]
version =3.0.1
date= 2011-2-20
developers = ACM_DIY
11
U appinfo appid 12345
G appinfo appid
I test value 110alcm
G test value
G userinfo password
G userinf name
I softversion version 3.0.5
G softversion version
U softversion date 2011-2-14
G softversion versio
G softversion Date
Sample Output
case 1:
update succeed.
12345
insert succeed.
110alcm
2536LR
not get the value.
insert failured.
3.0.1
update succeed.
not get the value.
not get the value.
Author
[FJAU]菜鳥(niǎo)
Source
ACM-DIY Group Contest 2011 Spring
Trie 處理插入查找，只是字符串輸入有點(diǎn)繁瑣。。。
1 #include <stdio.h>
2 #include <string.h>
3 #include <ctype.h>
4
5 #define TC 26
6 #define TM 400000
7 #define LEN 122
8 #define LIM 90000
9
10 int ibuf;
11 char buf[ LIM ][ LEN ];
12
13 struct _Trie
14 {
15 char isNode, isValue;
16 char *pData;
17 struct _Trie *ch[ TC ];
18 };
19 typedef struct _Trie Trie;
20
21 Trie *root;
22
23 Trie triemem[ TM ];
24 int iTriemem;
25
26 void trie_init() {
27 root = NULL;
28 iTriemem = 0;
29 }
30
31 Trie* trie_new() {
32 return triemem + iTriemem++;
33 }
34
35 /* 1 node, 0 other */
36 int getName( char *str ) {
37 int isNode = 0;
38 char ch;
39 do {
40 ch = getchar();
41 } while ( !( (('a'<=ch)&&(ch<='z')) || (ch=='[') ) );
42 if ( ch == '[' ) {
43 isNode = 1;
44 do {
45 ch = getchar();
46 } while ( (ch<'a') || ('z'<ch) );
47 }
48 while ( ('a'<=ch) && (ch<='z') ) {
49 *str++ = ch;
50 ch = getchar();
51 }
52 *str = 0;
53 return isNode;
54 }
55
56 void getValue( char *str ) {
57 char ch;
58 do {
59 ch = getchar();
60 } while ( (!isprint( ch )) || (ch=='=') || (ch==' ') || (ch=='\n') || (ch=='\t') );
61 while ( isprint( ch ) ) {
62 *str++ = ch;
63 ch = getchar();
64 }
65 *str = 0;
66 }
67
68 void getCmd( char *str ) {
69 do {
70 *str = getchar();
71 } while ( ((*str)<'A') || ('Z'<(*str)) );
72 str[ 1 ] = 0;
73 }
74
75 /* insert always, pData == NULL --- node, else name */
76 void trie_insert( Trie **pRoot, char *str, char *pData ) {
77 Trie **p = pRoot;
78 for ( ; ; ) {
79 if ( (*p) == NULL ) {
80 *p = trie_new();
81 memset( *p, 0, sizeof(Trie) );
82 }
83 if ( *str ) {
84 p = &( (*p)->ch[ (*str) - 'a' ] );
85 ++str;
86 }
87 else {
88 if ( pData ) {
89 (*p)->isValue = 1;
90 (*p)->pData = pData;
91 }
92 else {
93 (*p)->isNode = 1;
94 }
95 return;
96 }
97 }
98 }
99
100 /* ret 1, succ, other failed ppData == NULL node, else name */
101 int trie_find( Trie *root, char *str, char **ppData ) {
102 Trie *p = root;
103 for ( ; ; ) {
104 if ( p == NULL ) {
105 return 0;
106 }
107 if ( *str ) {
108 p = p->ch[ (*str) - 'a' ];
109 ++str;
110 }
111 else {
112 if ( ppData ) {
113 *ppData = p->pData;
114 return p->isValue;
115 }
116 else {
117 return p->isNode;
118 }
119 }
120 }
121 }
122
123 int main() {
124 int td, cd = 0, m, k;
125 char cmd[ 10 ], tmp[ LEN ], tmp2[ LEN+LEN ], node[ LEN ], *pData;
126 scanf( "%d", &td );
127 while ( td-- > 0 ) {
128 printf( "case %d:\n", ++cd );
129 ibuf = 0;
130 trie_init();
131 scanf( "%d", &m );
132 while ( m-- > 0 ) {
133 if ( getName( tmp ) ) {
134 trie_insert( &root, tmp, NULL );
135 strcpy( node, tmp );
136 }
137 else {
138 getValue( buf[ ibuf++ ] );
139 strcpy( tmp2, node );
140 strcat( tmp2, tmp );
141 trie_insert( &root, tmp2, buf[ ibuf-1 ] );
142 }
143 }
144 scanf( "%d", &k );
145 while ( k-- > 0 ) {
146 getCmd( cmd );
147 switch ( cmd[ 0 ] ) {
148 case 'U' :
149 getName( node );
150 strcpy( tmp2, node );
151 getName( tmp );
152 strcat( tmp2, tmp );
153 getValue( buf[ ibuf++ ] );
154 if ( trie_find( root, node, NULL ) && trie_find( root, tmp2, &pData ) ) {
155 trie_insert( &root, tmp2, buf[ ibuf-1 ] );
156 puts( "update succeed." );
157 }
158 else {
159 puts( "update failured." );
160 }
161 break;
162 case 'G' :
163 getName( node );
164 strcpy( tmp2, node );
165 getName( tmp );
166 strcat( tmp2, tmp );
167 if ( trie_find( root, node, NULL ) && trie_find( root, tmp2, &pData ) ) {
168 puts( pData );
169 }
170 else {
171 puts( "not get the value." );
172 }
173 break;
174 case 'I' :
175 getName( node );
176 strcpy( tmp2, node );
177 getName( tmp );
178 strcat( tmp2, tmp );
179 getValue( buf[ ibuf++ ] );
180 if ( trie_find( root, node, NULL ) && trie_find( root, tmp2, &pData ) ) {
181 puts( "insert failured." );
182 }
183 else {
184 trie_insert( &root, node, NULL );
185 trie_insert( &root, tmp2, buf[ ibuf-1 ] );
186 puts( "insert succeed." );
187 }
188 break;
189 }
190 }
191 }
192 return 0;
193 }
194