uva 630 - Anagrams (II)

⭐️

# 題目連結

• ZeroJudge
• 題目連結
• Online Judge
• uDebug

# 題目敘述

One of the preferred kinds of entertainment of people living in final stages of XX century is filling in the crosswords₁. Almost every newspaper and magazine has a column dedicated to entertainment but only amateurs₂ have enough after solving one crossword. Real professionals require more than one crossword for a week. And it is so dull — just crosswords and crosswords — while so many other riddles₃ are waiting out there. For those are special, dedicated magazines. There are also quite a few competitions to take part in, even reaching the level of World Championships. Anyway — a lot.

You were taken on by such a professional for whom riddle solving competing is just a job. He had a brilliant idea to use a computer in work not just to play games. Somehow anagrams found themselves first in the line. You are to write a program which searches for anagrams of given words, using a given vocabulary, tediously₄ filled with new words by yours employer.

# Input

The first line contains T the number of test cases. There is a blank line after this. Then, T test cases follow — each separated by a blank line. Each test case has the following structure:

< number of words in vocabulary >
< word 1 >
…
< word N >
< test word 1 >
…
< test word k >
END

< number of words in vocabulary > is an integer number N < 1000 . < word 1 > up to < word N > are words from the vocabulary. < test word 1 > up to < test word k > are the words to find anagrams₅ for. All words are lowercase (word ‘END’ means end of data — it is NOT a test word). You can assume all words are not longer than 20 characters.

# Output

For each < test word > — in the order in which it appeared — list the found anagrams in the following way:
Anagrams for: < test word >
< No >) < anagram >
…
< No > should be printed on 3 chars.

In case of failing to find any anagrams your output should look like this:
Anagrams for: < test word >
No anagrams for:

Print a blank line between datasets.

# Sample Input

1
8
atol
lato
microphotographics
rata
rola
tara
tola
pies
tola
kola
aatr
photomicrographics
END

# Sample Output

Anagrams for: tola
1) atol
2) lato
3) tola
Anagrams for: kola
No anagrams for: kola
Anagrams for: aatr
1) rata
2) tara
Anagrams for: photomicrographics
1) microphotographics

# Solution

#include <bits/stdc++.h>

using namespace std;

int main () {

    int T; cin >> T;

    while (T--) {

        int n; cin >> n;

        vector<pair<string, vector<char>>> vocab;

        string str;

        vector<char> tmp;

        for (int i=0; i<n; i++) {

            cin >> str;

            tmp.clear();

            for (char c : str) tmp.push_back(c);

            sort(tmp.begin(), tmp.end());

            vocab.push_back(make_pair(str, tmp));

        }

        while (cin >> str) {

            if (str == "END") break;

            vector<char> v;

            v.clear();  

            for (char c : str) v.push_back(c);

            sort(v.begin(), v.end());

            bool hasAnagram = false;

            int cnt = 1;

            cout << "Anagrams for: " << str << "\n";

            for (auto p : vocab) {

                if (p.second == v) {

                    cout << "  " << cnt++ <<") " << p.first << "\n";

                    hasAnagram = true; 

                }

            }

            if (!hasAnagram) cout << "No anagrams for: " << str << "\n";

        }

        if (T != 0) cout << "\n";

    }

    return 0;

}

# 註解

1. crossword n. 縱橫填字遊戲

A game in which you write words that are the answers to questions in a pattern of black and white squares.
ex. I do the Times crossword every morning.

2. amateurs

• adj. 業餘愛好的，非職業的
  Taking part in an activity for pleasure, not as a job.
  ex. He was an amateur singer until the age of 40, when he turned professional.
• n. 外行；粗通（某一行）的人
  Someone who does not have much skill in what they do.
  ex. I won’t be giving them any more work - they’re a bunch of amateurs.

3. riddle

• n. 謎；謎語
  A type of question that describes something in a difficult and confusing way and has a clever or funny answer, often asked as a game.
• n. 奧秘；費解之事
  Something that is confusing, or a problem that is difficult to solve.
  ex. Scientists may have solved the riddle of Saturn’s rings.
• v. 使布滿洞孔
  To make a lot of holes in something.
  ex. The anti-aircraft guns riddled the plane’s wings with bullets.

4. tediously adv. 單調乏味地，無趣地

In a boring way that continues for a long time.
ex. Many people work tediously at a boring job for many years.

5. anagram n. 相同字母異序詞

A word or phrase made by using the letters of another word or phrase in a different order
ex. “Neat” is an anagram of “a net”.