一、思路:
1、将结构化文档的每一行处理成一个节点(可定义一个结构体,成员包含标签tag、属性id、层级level、祖先所在行数father)。
2、然后整个结构化文档就成了一个树形结构,可从任一节点轻松访问到祖先节点。
3、从1到n行遍历文档,将后代选择器从后往前依次与第i行所在节点及其祖先节点匹配。
4、【提示】多级的后代选择器在匹配时,可以采用贪心的策略:除最后一级外,前面部分都可以尽量匹配层级小的元素(在树中较深的节点)。
一开始没懂提示在说啥,后来做出来只有80分,百度了一下才知道:祖先的祖先仍是祖先。
例如 div p 这个命令,如果p是第10级,div是第1级,这个p也能被选中。
5、注意:tag对大小写不敏感,id属性对大小写敏感。
二、代码:
对C++STL的string类型和stringstream流不熟悉,因此虽是C++代码,但有点偏C的风格。
1 #include<cstdio> 2 #include<vector> 3 #include<stack> 4 #include<cstring> 5 #include<iostream> 6 using namespace std; 7 const int N=101; 8 const int M=100; 9 struct node 10 { 11 char tag[M],id[M]; 12 int level,father; 13 }; 14 node text[N]; 15 bool equal(char*str1,char*str2) 16 { 17 while(*str1||*str2){ 18 if(*str1>='0'&&*str1<='9'){ 19 if(*str1!=*str2)return false; 20 } 21 else{ 22 if(*str1>'Z')*str1-=32; 23 if(*str2>'Z')*str2-=32; 24 if(*str1!=*str2)return false; 25 } 26 str1++;str2++; 27 } 28 return true; 29 } 30 int main() 31 { 32 //freopen("in.txt","r",stdin); 33 int n,m; 34 stack<pair<int,int> >fa; 35 fa.push(make_pair(-1,-1)); 36 scanf("%d%d",&n,&m); 37 getchar(); 38 for(int i=1;i<=n;i++){ 39 char str[M]; 40 //gets(str); 41 fgets(str,M,stdin); 42 //cout<<i<<' '<<str<<endl; 43 int j=0; 44 while(str[j]=='.')j++; 45 text[i].level=j/2; 46 pair<int,int>par=fa.top(); 47 //cout<<par.first<<' '<<par.second<<endl; 48 while(par.second>=text[i].level){ 49 fa.pop();par=fa.top(); 50 //cout<<par.first<<' '<<par.second<<endl; 51 } 52 //cout<<endl; 53 text[i].father=par.first; 54 if(sscanf(str+j,"%s%s",text[i].tag,text[i].id)==1)text[i].id[0]=0; 55 fa.push(make_pair(i,text[i].level)); 56 } 57 /* 58 for(int i=1;i<=n;i++){ 59 node&t=text[i]; 60 cout<<t.father<<' '<<t.level<<' '<<t.tag<<' '<<t.id<<endl; 61 } 62 */ 63 //getchar(); 64 while(m--){ 65 int i=0; 66 vector<int>ans; 67 char c,order[M],temp[M]; 68 while((c=getchar())!=EOF&&c!='\n'){ 69 order[i++]=c; 70 } 71 order[i]=0; 72 int len=i; 73 for(int k=1;k<=n;k++){ 74 int now=k,flag=0; 75 i=len; 76 while(1){ 77 while(i>=0&&order[i]!=' ')i--; 78 sscanf(order+i+1,"%s",temp); 79 if(temp[0]=='#'){ 80 if(strcmp(temp,text[now].id)==0){ 81 flag=1; 82 if(i==-1)ans.push_back(k); 83 i--; 84 } 85 else if(flag==0)i=-1; 86 else i++; 87 } 88 else { 89 if(equal(temp,text[now].tag)){ 90 flag=1; 91 if(i==-1)ans.push_back(k); 92 i--; 93 } 94 else if(flag==0)i=-1; 95 else i++; 96 } 97 now=text[now].father; 98 if(now==-1)i=-1; 99 if(i<0)break; 100 } 101 } 102 printf("%d",ans.size()); 103 for(i=0;i<ans.size();i++){ 104 printf(" %d",ans[i]); 105 } 106 printf("\n"); 107 } 108 return 0; 109 }