ZOJ 3674 Search in the Wiki 字典树+set+map映射

九野的博客，转载请注明出处：http://blog.csdn.net/acmmmm/article/details/12844529

题意：

n个单词

下面n*2行， 第一个为单词，第二行为该单词的关联词汇

最后一行询问： 字典序输出 这些单词关联的 公共关联词汇

思路：

做起来有些麻烦，没有太多思路，模拟做即可

#include <iostream>#include <cstdio>#include <cstring>#include <set>#include <queue>#include <algorithm>#include <cstdlib>#include <vector>#include <math.h>#include <map>#define ll intusing namespace std;inline ll Max(ll a, ll b){return a>b?a:b;}#define Word_Len 101000#define Sigma_size 53struct kkkk{char name[201];}S[Word_Len];bool cmp(kkkk a,kkkk b){return strcmp(a.name,b.name)<0;} struct Trie{int ch[Word_Len][Sigma_size]; //Word_Len是字典树的节点数 若都是小写字母Sigma_size=26int len[Word_Len]; //这个节点下有几个单词int pre[Word_Len]; // 这个节点附带的信息，初始化为0表示这个节点不存在单词，所以节点带的信息必须!=0char ccc[Word_Len];int sz ; //当前节点数Trie() //初始化字典树{ sz = 1; memset(ch, 0, sizeof(ch)); memset(pre, -1, sizeof(pre)); memset(len, 0, sizeof(len));}//初始化int idx(char c){if('a'<=c && c<='z') return c-'a';else return c - 'A' + 26; } //字符串编号int insert(char *s){ //把v数字加给 s单词最后一个字母int u = 0, Len = strlen(s);for(int i = 0; i < Len; i++){int c = idx(s[i]);if(!ch[u][c])     //节点不存在就新建后附加{pre[sz] = u;ccc[sz] = s[i];ch[u][c] = sz++;}u = ch[u][c];}len[u] = Len;//现在的u就是这个单词的最后一个位置return u;}int find_word(char *s){int u = 0, len = strlen(s);bool creat = false;for(int i = 0; i < len; i++){int c = idx(s[i]);if(!ch[u][c])//节点不存在return 0;u = ch[u][c];}return u;}void zouni(int u, int i){int Len = len[u] - 1;S[i].name[Len +1] = '\0';while(pre[u] != -1){S[i].name[Len] = ccc[u];u = pre[u];Len --;}}};Trie ac;ll n;set<int>myset[250],ans;set<int> ::iterator p;map<int,int> mymap;char s[250],s2[250];int aa[Word_Len];int st[Word_Len];int main(){ll i, que, num;while(~scanf("%d",&n)){for(i=0;i<=n;i++)myset[i].clear();mymap.clear();for(i=1;i<=n;i++){scanf("%s",s);getchar();num = ac.insert(s);mymap.insert(pair<int,int>(num, i));gets(s2);int len = strlen(s2), j = 0;memset(s,0,sizeof(s));for(int k = 0; k <= len; k++){if(s2[k] != ' ' && s2[k]!='\0')s[j++] = s2[k];else {s[j] = '\0';myset[i].insert( ac.insert(s) );j = 0;memset(s,0,sizeof(s));}}}scanf("%d",&que);getchar();while(que--){ans.clear(); gets(s2);n = 0;int len = strlen(s2), j = 0;memset(s,0,sizeof(s));memset(aa,0,sizeof(aa));for(int k = 0; k <= len; k++){if(s2[k]!=' ' &&  s2[k]!='\0' )s[j++] = s2[k];else {s[j] = '\0';num = ac.find_word(s);num = mymap.find(num)->second;for( p = myset[num].begin(); p!=myset[num].end(); p++){int temp = *p;aa[ temp ]++;ans.insert(temp);}j = 0;n ++ ;memset(s,0,sizeof(s));}}int top = 0;for(p = ans.begin(); p!=ans.end(); p++){int temp = *p;if(aa[ temp ]== n)st[top++] = temp;}if(top == 0){ printf("NO\n"); continue; }for(i = 0; i < top; i++){memset(S[i].name,0,sizeof(S[i].name));ac.zouni(st[i], i);}sort(S, S+top,cmp);for(i=0;i<top-1;i++)printf("%s ",S[i].name);printf("%s\n",S[top-1].name);}}return 0;}/*4fishagile animal feiuahsd a b c d feiuahsdfeiuahsdfeiuahsdhorseswift animal feiuahsd a b c d feiuahsdfeiuahsdfeiuahsdeaglefierce animal sdf feiuahsd a b c d feiuahsdfeiuahsdfeiuahsdKyuubeealien incubator fdasxcgrf dfg feiuahsd asf a b c d feiuahsdfeiuahsdfeiuahsd2fish horse eaglefish horse eagle Kyuubee*/