http://acm.hdu.edu.cn/showproblem.php?pid=1113

Problem Description

In millions of newspapers across the United States there is a word game called Jumble. The object of this game is to solve a riddle, but in order to find the letters that appear in the answer it is necessary to unscramble four words. Your task is to write a program that can unscramble words.

Input

The input contains four parts:

1. a dictionary, which consists of at least one and at most 100 words, one per line;
2. a line containing XXXXXX, which signals the end of the dictionary;
3. one or more scrambled `words‘ that you must unscramble, each on a line by itself; and
4. another line containing XXXXXX, which signals the end of the file.

All words, including both dictionary words and scrambled words, consist only of lowercase English letters and will be at least one and at most six characters long. (Note that the sentinel XXXXXX contains uppercase X‘s.) The dictionary is not necessarily in sorted order, but each word in the dictionary is unique.


Output

For each scrambled word in the input, output an alphabetical list of all dictionary words that can be formed by rearranging the letters in the scrambled word. Each word in this list must appear on a line by itself. If the list is empty (because no dictionary words can be formed), output the line ``NOT A VALID WORD" instead. In either case, output a line containing six asterisks to signal the end of the list.


Sample Input

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
******
NOT A VALID WORD
******
course
******

题意：先给你一些单词作为字典，在给一系列的单词查找字典中是否有这些单词（注意查找的单词，一个单词中的字母顺序是可以变得，也就是说单词之间只要字母是一样的不用考虑顺序一样都要输出）；如果字典中沒有字母都相同的單詞就輸出“NOT A VALID WORD”，並且每次都要輸出一行“******”；

解題思路：

map容器是一個一對一的向量容器（詳細了解http://blog.csdn.net/keshacookie/article/details/19847781）

>>> 首先，輸入一系列字典單詞，碰到“XXXXXX”結束；這些單詞作為向量的前端（後端也行，個人喜好，思路不要弄錯就行了）， 在每輸入一個字典單詞的時候，保存單詞的原態， 然後再對單詞排序，排序后的單詞作為向量的後端；

>>> 然後，輸入加密后的單詞，先對加密單詞進行排序，然後對map裡面存儲的字典單詞向量的後端進行比較（遍歷一遍就OK了）；

>>> 對應輸出就行了；

代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>       //添加map頭文件
#include <string>
#include <algorithm>
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

int flag;
string s1, s2;    //字符串容器；
map <string, string> mp;   //map容器
map <string, string> ::iterator it;  //map迭代器

int main()
{
    mp.clear();   //清空map容器
    while(cin >> s1) {   //輸入字典單詞
        if(s1 == "XXXXXX") break;
        s2 = s1;     //保存單詞的原來狀態
        sort(s1.begin(), s1.end());
        mp[s2] = s1;   //s1, s2形成向量，存儲在map容器中
    }
    while(cin >> s1) {  //輸入加密單詞
        if(s1 == "XXXXXX") break;
        flag = 0;
        sort(s1.begin(), s1.end());
        for(it=mp.begin(); it != mp.end(); it++) { //遍歷，對字符串進行比較
            string tmp = (*it).second;  //map中first，second分別代表向量的前後端
            if(s1 == tmp) {
                cout << (*it).first << endl;
                flag = 1;
            }
        }
        if(!flag) cout << "NOT A VALID WORD" << endl;
        cout << "******" << endl;
    }
    return 0;
}

HDU 1113 Word Amalgamation （map 容器 + string容器）