B. Substrings Sort

Codeforces

IDCF988B

Time1000ms

Memory256MB

Difficulty—

sortingsstrings

English · Original

Chinese · Translation

Formal · Original

You are given $n$ strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its _substrings_. String $a$ is a _substring_ of string $b$ if it is possible to choose several _consecutive_ letters in $b$ in such a way that they form $a$. For example, string "_for_" is contained as a _substring_ in strings "_codeforces_", "_for_" and "_therefore_", but is not contained as a _substring_ in strings "_four_", "_fofo_" and "_rof_". ## Input The first line contains an integer $n$ ($1 \le n \le 100$) — the number of strings. The next $n$ lines contain the given strings. The number of letters in each string is from $1$ to $100$, inclusive. Each string consists of lowercase English letters. Some strings might be equal. ## Output If it is impossible to reorder $n$ given strings in required order, print "_NO_" (without quotes). Otherwise print "_YES_" (without quotes) and $n$ given strings in required order. [samples] ## Note In the second example you cannot reorder the strings because the string "_abab_" is not a _substring_ of the string "_abacaba_".

你被给定 $n$ 个字符串。每个字符串由小写英文字母组成。请将这些字符串重新排列（排序），使得对于每一个字符串，所有排在它前面的字符串都是它的 _子串_。字符串 $a$ 是字符串 $b$ 的 _子串_，当且仅当可以在 $b$ 中选出若干个 _连续_ 的字母，使其恰好构成 $a$。例如，字符串 "_for_" 是字符串 "_codeforces_"、"_for_" 和 "_therefore_" 的 _子串_，但不是字符串 "_four_"、"_fofo_" 和 "_rof_" 的 _子串_。第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 100$) —— 字符串的数量。接下来 $n$ 行包含给定的字符串。每个字符串的字母数量在 $1$ 到 $100$ 之间（含）。每个字符串均由小写英文字母组成。某些字符串可能相等。如果无法将给定的 $n$ 个字符串按要求重新排列，请输出 "_NO_"（不含引号）。否则，请输出 "_YES_"（不含引号），并在下一行按要求的顺序输出这 $n$ 个字符串。在第二个示例中，你无法重新排列字符串，因为字符串 "_abab_" 不是字符串 "_abacaba_" 的 _子串_。 ## Input 第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 100$) —— 字符串的数量。接下来 $n$ 行包含给定的字符串。每个字符串的字母数量在 $1$ 到 $100$ 之间（含）。每个字符串均由小写英文字母组成。某些字符串可能相等。 ## Output 如果无法将给定的 $n$ 个字符串按要求重新排列，请输出 "_NO_"（不含引号）。否则，请输出 "_YES_"（不含引号），并在下一行按要求的顺序输出这 $n$ 个字符串。 [samples] ## Note 在第二个示例中，你无法重新排列字符串，因为字符串 "_abab_" 不是字符串 "_abacaba_" 的 _子串_。

Let $ S = \{s_1, s_2, \dots, s_n\} $ be a multiset of $ n $ strings over the alphabet $ \Sigma = \{a, b, \dots, z\} $. **Goal:** Determine if there exists a permutation $ \sigma \in S_n $ such that for all $ i \in \{2, 3, \dots, n\} $, $$ s_{\sigma(i-1)} \text{ is a substring of } s_{\sigma(i)}. $$ Equivalently, find an ordering $ t_1, t_2, \dots, t_n $ of the strings in $ S $ such that: $$ \forall i \in \{2, \dots, n\}, \quad t_{i-1} \sqsubseteq t_i, $$ where $ a \sqsubseteq b $ denotes that string $ a $ is a contiguous substring of string $ b $. **Constraints:** - $ 1 \leq n \leq 100 $ - Each string has length between 1 and 100, inclusive. - Strings may be duplicated. **Output:** - If such an ordering exists: Print "YES", followed by $ t_1, t_2, \dots, t_n $. - Otherwise: Print "NO". **Note:** The substring relation $ \sqsubseteq $ is **not symmetric** and **not total**; it is reflexive and transitive. For the ordering to exist, the multiset must admit a total order under $ \sqsubseteq $.

Samples

Input #1

5
a
aba
abacaba
ba
aba

Output #1

YES
a
ba
aba
aba
abacaba

Input #2

5
a
abacaba
ba
aba
abab

Output #2

NO

Input #3

3
qwerty
qwerty
qwerty

Output #3

YES
qwerty
qwerty
qwerty

API Response (JSON)

{
  "problem": {
    "name": "B. Substrings Sort",
    "description": {
      "content": "You are given $n$ strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its _",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF988B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given $n$ strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its _...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定 $n$ 个字符串。每个字符串由小写英文字母组成。请将这些字符串重新排列（排序），使得对于每一个字符串，所有排在它前面的字符串都是它的 _子串_。\n\n字符串 $a$ 是字符串 $b$ 的 _子串_，当且仅当可以在 $b$ 中选出若干个 _连续_ 的字母，使其恰好构成 $a$。例如，字符串 \"_for_\" 是字符串 \"_codeforces_\"、\"_for_\" 和 \"_therefore_\"...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ S = \\{s_1, s_2, \\dots, s_n\\} $ be a multiset of $ n $ strings over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $.\n\n**Goal:** Determine if there exists a permutation $ \\sigma \\in S_n $ such that f...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments