首页 > 代码库 > zoj3826 Hierarchical Notation (字符串模拟)
zoj3826 Hierarchical Notation (字符串模拟)
In Marjar University, students in College of Computer Science will learn EON (Edward Object Notation), which is a hierarchical data format that uses human-readable text to transmit data objects consisting of attribute-value pairs. The EON was invented by Edward, the headmaster of Marjar University.
The EON format is a list of key-value pairs separated by comma ",", enclosed by a couple of braces "{" and "}". Each key-value pair has the form of "<key>":"<value>". <key> is a string consists of alphabets and digits. <value> can be either a string with the same format of <key>, or a nested EON.
To retrieve the data from an EON text, we can search it by using a key. Of course, the key can be in a nested form because the value may be still an EON. In this case, we will use dot "." to separate different hierarchies of the key.
For example, here is an EON text:
{"headmaster":"Edward","students":{"student01":"Alice","student02":"Bob"}}
- For the key "headmaster", the value is "Edward".
- For the key "students", the value is {"student01":"Alice","student02":"Bob"}.
- For the key "students"."student01", the value is "Alice".
As a student in Marjar University, you are doing your homework now. Please write a program to parse a line of EON and respond to several queries on the EON.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains an EON text. The number of colons ":" in the string will not exceed 10000 and the length of each key and non-EON value will not exceed 20.
The next line contains an integer Q (0 <= Q <= 1000) indicating the number of queries. Then followed by Q lines, each line is a key for query. The querying keys are in correct format, but some of them may not exist in the EON text.
The length of each hierarchy of the querying keys will not exceed 20, while the total length of each querying key is not specified. It is guaranteed that the total size of input data will not exceed 10 MB.
Output
For each test case, output Q lines of values corresponding to the queries. If a key does not exist in the EON text, output "Error!" instead (without quotes).
Sample Input
1{"hm":"Edward","stu":{"stu01":"Alice","stu02":"Bob"}}4"hm""stu""stu"."stu01""students"Sample Output
"Edward"{"stu01":"Alice","stu02":"Bob"}"Alice"Error!
题意： 牡丹江的H题， 写一个很类似python的字典的东西，然后给出键值输出对应的值，可以嵌套。ps 好喜欢python这样的自由、简洁，打完这星期国赛就专研一下python
思路： 使劲模拟一遍就ok啦，一开始tle了，看了别人题解，原来应该hash一下字符串再存入map中的，改hash后150ms就过了
#pragma comment(linker,"/STACK:1024000000,1024000000")#include <bits/stdc++.h>using namespace std;const int N = 1000010;char s[N],query[N];int p,sz,qsz;struct _node{ int val_l,val_r; map<string,int> mp; void clear() { val_l=val_r=0; mp.clear(); }}node[N];int cnt;void readname(char *s,int sz,int &l,int &r){ l=p++; while(p<sz && s[p]!=‘"‘) p++; r=p++;// cout<<l<<‘ ‘<<r<<‘ ‘<<s[l]<<‘ ‘<<s[r]<<endl;}void prints(int l,int r){ while(l<=r && l<sz) putchar(s[l++]); puts("");}void build(int root){ node[root].val_l=p++; if(s[p]==‘}‘) goto bk; while(p<sz) { int l,r; readname(s,sz,l,r); string key(s,l,r-l+1);// cout<<l<<‘ ‘<<r<<‘ ‘<<root<<‘ ‘<<key<<endl; node[root].mp[key]=cnt;// cout<<node[root].mp[key]<<endl; node[cnt++].clear(); p++; // : if(s[p]==‘{‘) build(cnt-1); else readname(s,sz,node[cnt-1].val_l,node[cnt-1].val_r); if(s[p]==‘}‘) break; else p++; // , } bk: node[root].val_r=p++;}void getans(int root,int &ansl,int &ansr){ int l,r; while(true) { readname(query,qsz,l,r); string str(query,l,r-l+1); if(node[root].mp.find(str)!=node[root].mp.end()) root=node[root].mp[str]; else { root=-1; break; } if(query[p]!=‘.‘) break; p++; } if(root==-1) ansl=ansr=-1; else ansl=node[root].val_l,ansr=node[root].val_r;}void run(){// scanf("%s",s); gets(s); p=0,sz=strlen(s); node[0].clear(); cnt=1; build(0); int q;char c; scanf("%d",&q); scanf("%c",&c); while(q--) {// scanf("%s",query); gets(query); qsz=strlen(query); p=0; int l,r; getans(0,l,r); if(l==-1) puts("Error!"); else prints(l,r); }// cout<<endl;// for(map<string,int>::iterator it=node[0].mp.begin(); it!=node[0].mp.end(); it++)// cout<<it->first<<‘ ‘<<it->second<<endl;}void test(){ scanf("%s",s); p=0; prints(0,5);}int main(){ #ifdef LOCAL freopen("in","r",stdin); #endif// test(); int _;char c; scanf("%d",&_); scanf("%c",&c); while(_--) run(); return 0;}
不过还是这个大神写的比较简洁耗内存少
http://blog.csdn.net/keshuai19940722/article/details/40039745
#include <cstdio>#include <cstring>#include <map>#include <vector>#include <algorithm>using namespace std;typedef unsigned long long ll;typedef pair<int,int> pii;const int maxn = 2000000;const ll x = 123;int N, Q, mv;char op[maxn], s[maxn];map<ll, pii> G;inline int idx(char ch) { if (ch >= ‘0‘ && ch <= ‘9‘) return ch - ‘0‘; else if (ch >= ‘A‘ && ch <= ‘Z‘) return ch - ‘A‘ + 10; else if (ch >= ‘a‘ && ch <= ‘z‘) return ch - ‘a‘ + 36; else if (ch == ‘.‘) return 62; return 63;}void solve (ll u) { ll tmp = u; while (s[mv] != ‘}‘) { mv++; if (s[mv] == ‘}‘) return; u = tmp; while (s[mv] != ‘:‘) u = u * x + idx(s[mv++]); int l = ++mv; if (s[mv] == ‘{‘) solve(u * x + 62LL); else while (s[mv+1] != ‘,‘ && s[mv+1] != ‘}‘) mv++; G[u] = make_pair(l, mv); mv++; }}int main () { int cas; scanf("%d", &cas); while (cas--) { scanf("%s", s); mv = 0; G.clear(); solve(0); scanf("%d", &Q); for (int i = 1; i <= Q; i++) { scanf("%s", op); ll ret = 0; int len = strlen(op); for (int i = 0; i < len; i++) ret = ret * x + idx(op[i]); if (G.count(ret)) { pii u = G[ret]; for (int i = u.first; i <= u.second; i++) printf("%c", s[i]); printf("\n"); } else printf("Error!\n"); } } return 0;}
zoj3826 Hierarchical Notation (字符串模拟)