122 - ZOJ Monthly, November 2012-I Search in the Wiki 地图+set 一对多
122 - ZOJ Monthly, November 2012-I Search in the Wikimap+set 一对多/*map+set一个对应多个把“解释串”（
122 - ZOJ Monthly, November 2012-I Search in the Wiki map+set 一对多
/*map+set一个对应多个把“解释串”（第二个串） 中的每个单词分开 用每一个单词对应第一个串如此"解释串"中的某个单词就对应了一个集合 这个集合里存的是第一个串 这个单词就是这些串的公共单词 一开始一个劲的段错误 strcpy(ans[ac],ss[i]); 原因是 ans数组开小了 复制的时候给爆了*/#include<stdio.h>#include<string.h>#include<stdlib.h>#include<set>#include<string>#include<map>#include<iostream>using namespace std;char s1[300],s2[300],ss[5000][300];char s[1000][300],ans[5000][300]; int love(const void *a,const void *b){return strcmp((char *)a,(char *)b);}int main(){int n,m,i,j,k,cnt,cnt1,ac,flag;map<string,set<string> >mp; while(scanf("%d",&n)!=EOF){ mp.clear();getchar();cnt1=0;for(i=1;i<=n;i++){gets(s1);gets(s2);int t=0;for(j=0;s2[j]!='\0';j++)//把第二个串 分成一个一个的单词放进ss中{if(s2[j]==' '){ss[cnt1][t]='\0';mp[ss[cnt1]].insert(s1);t=0;cnt1++;continue;}ss[cnt1][t++]=s2[j];}ss[cnt1][t]='\0'; mp[ss[cnt1]].insert(s1);cnt1++;}scanf("%d",&m);getchar();while(m--){ gets(s2);cnt=0;flag=0;int t=0;for(i=0;s2[i]!='\0';i++){if(s2[i]==' '){s[cnt][t]='\0';cnt++;t=0;continue;} s[cnt][t++]=s2[i];}s[cnt][t]='\0';cnt++;//cnt个小串在s中 cnt1个解释串在ss中ac=0;for(i=0;i<cnt1;i++){for(j=0;j<cnt;j++){if(mp[ss[i]].find(s[j])==mp[ss[i]].end())break;}if(j==cnt){ //ans[ac++]=ss[i];flag=1;strcpy(ans[ac],ss[i]);ac++;}}if(flag==0)printf("NO\n");else{ qsort(ans,ac,sizeof(ans[0]),love);//排序以便找出重复的 int num=1; for(i=1;i<ac;i++)//去掉重复的 { if(strcmp(ans[i],ans[i-1])!=0) strcpy(ans[num++],ans[i]); } printf("%s",ans[0]); for(i=1;i<num;i++) printf(" %s",ans[i]); printf("\n");}}}return 0;}
