学步园

最近用了下STL，觉得很多工作轻松了不少~

这里结合一道题说明！

混杂游戏

Time Limit:1000MS  Memory Limit:65536K
Total Submit:80 Accepted:26

Description

以前流行玩一种文字游戏——混杂。所谓混杂就是在一个已知的答案中解读一串被打乱的字符串。你的任务是写一个程序，解读这个难题。

Input

输入的第一行是一个整数T( 1 <= T <= 100 )，表示有几组输入数
据。
每组输入由4部分组成：
(1)一个字典，最多包含2000个单词，每个单词一行。
(2)一行字符串"XXXXXX"，作为字典部分的结束标志。
(3)1个或多个( 最多2000个 )需要解读的字符串。每个一行。
(4) 一行字符串"XXXXXX"，作为解读部分的结束标志。
以上的每个单词都只有小写字母组成，最长不超过10。字典不一定是有序的。单词是唯一的。

Output

每组输出中，对应每个解读串A，如果有一个串B和A由相同的字母组成，则认为B可以解读A。在字典中找到所有可以解读A的串，并且以字典顺序输出,每个单词一行，然后输出一行"******"。如果没有找到符合条件的单词串，就输出一行"NO ONE"，然后输出一行"******"。

Sample Input

1
tarp
given
score
refund
only
trap
work
earn
course
pepper
part
XXXXXX
resco
nfudre
aptr
sett
oresuc
XXXXXX

Sample Output

score
******
refund
******
part
tarp
trap
******
NO ONE 
******
course
******

Source

典型的字典树，yes?

here I tried to use a little easy method~

record every letter's occurance in each word

and use stl in vector, use it to save string in dictionary

#include <iostream><br /> #include <algorithm><br /> #include <string><br /> #include <vector><br /> #include<map><br /> using namespace std;<br /> #define M 2005</p> <p>int a[M][26],b[26];<br /> vector<string>Q;</p> <p>void main()<br /> {<br /> int T;<br /> scanf("%d",&T);<br /> string str;<br /> int flag;<br /> int i,j,index;<br /> while(T--)<br /> {<br /> Q.clear();<br /> index=0;<br /> while(cin>>str&&str!="XXXXXX")<br /> {<br /> Q.push_back(str);<br /> index++;<br /> }<br /> sort(Q.begin(),Q.end());<br /> for(i=0;i<index;i++)<br /> {<br /> for (j=0;j<26;j++)<br /> a[i][j]=0;<br /> for(j=0;j<Q[i].length();j++)<br /> a[i][Q[i][j]-'a']++;<br /> }<br /> while(cin>>str&&str!="XXXXXX")<br /> {<br /> for(i=0;i<26;i++)<br /> b[i]=0;<br /> for(i=0;i<str.length();i++)<br /> b[str[i]-'a']++;<br /> flag=0;<br /> for(i=0;i<index;i++)<br /> {<br /> for(j=0;j<26;j++)<br /> {<br /> if(a[i][j]!=b[j])<br /> break;<br /> }<br /> if(j==26)<br /> {<br /> cout<<Q[i]<<endl;<br /> flag=1;<br /> }<br /> }<br /> if(!flag)<br /> cout<<"NO ONE"<<endl;<br /> cout<<"******"<<endl;<br /> }<br /> }<br /> }

法二.use multimap to record as hash table

#include <iostream><br /> #include <algorithm><br /> #include <string><br /> #include <vector><br /> #include<map><br /> using namespace std;</p> <p>multimap<string,string>dic;<br /> multimap<string,string>::iterator it,it2;</p> <p>void main()<br /> {<br /> int T;<br /> scanf("%d",&T);<br /> string str;<br /> int flag;<br /> while(T--)<br /> {<br /> int sub=1;<br /> dic.clear();<br /> while(cin>>str&&str!="XXXXXX")<br /> {<br /> string temp=str;<br /> sort(str.begin(),str.end());<br /> //dic[str]=temp;<br /> dic.insert(pair<string,string>(str,temp));<br /> }<br /> string rec[2000];<br /> while(cin>>str&&str!="XXXXXX")<br /> {<br /> sort(str.begin(),str.end());</p> <p> flag=0;<br /> it=dic.find(str);<br /> if(it==dic.end())<br /> cout<<"NO ONE"<<endl;<br /> else<br /> {<br /> int index=0;<br /> for(it2=it;it2!=dic.end();it2++)<br /> {<br /> if((*it2).first!=str)<br /> break;<br /> else rec[index++]=(*it2).second;<br /> }<br /> sort(rec,rec+index);<br /> for(int i=0;i<index;i++)<br /> cout<<rec[i]<<endl;<br /> //cout<<(*it2).second<<endl;<br /> }<br /> cout<<"******"<<endl;<br /> }<br /> }<br /> }