148. Internet Anagram Server

Codeforces

IDCF10269148

Time15000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You have a string, consisting of at most seven characters, not including spaces. You want to find all of the anagrams of the string. A string $t$ is defined as an anagram of a string $s$ if an only if the characters of $s$, in sorted order, not including spaces, are equal to the characters of $t$, in sorted order, not including spaces. You're also given a dictionary of $n$ words. An anagram is considered a _valid anagram_ if it consists of only space-separated words that are in the dictionary. For example, if the dictionary was the English dictionary, _hello_ and _hello world_ would be valid anagrams, but _he llo_ and _helloworld_ would not be valid anagrams. Given the string, and the dictionary, print all of the valid anagrams of the string, in alphabetical order. The first line of input contains a single string $s$, possibly containing spaces. $s$ will have less than or equal to seven characters, not including spaces. The next line of input consists of a single positive integer $n$, indicating how many words are in the dictionary. The next $n$ lines each contain a word not containing spaces: each dictionary entry. Output all of the words or phrases that are valid anagrams of the given string, in alphabetical order. Make sure not to repeat words, i.e. all of the answers should be distinct. ## Input The first line of input contains a single string $s$, possibly containing spaces. $s$ will have less than or equal to seven characters, not including spaces.The next line of input consists of a single positive integer $n$, indicating how many words are in the dictionary.The next $n$ lines each contain a word not containing spaces: each dictionary entry. ## Output Output all of the words or phrases that are valid anagrams of the given string, in alphabetical order. Make sure not to repeat words, i.e. all of the answers should be distinct. [samples]

**Definitions** Let $ s $ be a string over an alphabet $ \Sigma $, with $ |s|_{\text{non-space}} \leq 7 $. Let $ D = \{w_1, w_2, \dots, w_n\} $ be a finite dictionary of distinct words over $ \Sigma $, each $ w_i \in \Sigma^* $ and $ w_i $ contains no spaces. Let $ \text{sort}(x) $ denote the multiset of characters of string $ x $, sorted lexicographically, ignoring spaces. A string $ t $ is an **anagram** of $ s $ if $ \text{sort}(t) = \text{sort}(s) $. A string $ t $ is a **valid anagram** if: - $ t $ is a concatenation of one or more space-separated words from $ D $, - $ t $ contains no leading, trailing, or consecutive spaces, - $ \text{sort}(t) = \text{sort}(s) $. **Constraints** 1. $ |s|_{\text{non-space}} \leq 7 $ 2. $ n \in \mathbb{Z}^+ $, $ n \leq 1000 $ (implied by context) 3. Each word in $ D $ has no spaces and length $ \geq 1 $ 4. All output anagrams must be distinct **Objective** Find the set $ \mathcal{A} = \{ t \mid t \text{ is a valid anagram of } s \} $. Output all $ t \in \mathcal{A} $ in lexicographical (alphabetical) order.

API Response (JSON)

{
  "problem": {
    "name": "148. Internet Anagram Server",
    "description": {
      "content": "You have a string, consisting of at most seven characters, not including spaces. You want to find all of the anagrams of the string. A string $t$ is defined as an anagram of a string $s$ if an only if",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 15000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269148"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have a string, consisting of at most seven characters, not including spaces. You want to find all of the anagrams of the string. A string $t$ is defined as an anagram of a string $s$ if an only if...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s $ be a string over an alphabet $ \\Sigma $, with $ |s|_{\\text{non-space}} \\leq 7 $.  \nLet $ D = \\{w_1, w_2, \\dots, w_n\\} $ be a finite dictionary of distinct words over $ \\Sig...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments