D. Restoration of string

Codeforces

IDCF890D

Time2000ms

Memory256MB

Difficulty—

graphsgreedystrings

English · Original

Chinese · Translation

Formal · Original

A substring of some string is called the most frequent, if the number of its occurrences is not less than number of occurrences of any other substring. You are given a set of strings. A string (not necessarily from this set) is called good if all elements of the set are the most frequent substrings of this string. Restore the non-empty good string with minimum length. If several such strings exist, restore lexicographically minimum string. If there are no good strings, print "_NO_" (without quotes). A substring of a string is a contiguous subsequence of letters in the string. For example, "_ab_", "_c_", "_abc_" are substrings of string "_abc_", while "_ac_" is not a substring of that string. The number of occurrences of a substring in a string is the number of starting positions in the string where the substring occurs. These occurrences could overlap. String _a_ is lexicographically smaller than string _b_, if _a_ is a prefix of _b_, or _a_ has a smaller letter at the first position where _a_ and _b_ differ. ## Input The first line contains integer _n_ (1 ≤ _n_ ≤ 105) — the number of strings in the set. Each of the next _n_ lines contains a non-empty string consisting of lowercase English letters. It is guaranteed that the strings are distinct. The total length of the strings doesn't exceed 105. ## Output Print the non-empty good string with minimum length. If several good strings exist, print lexicographically minimum among them. Print "_NO_" (without quotes) if there are no good strings. [samples] ## Note One can show that in the first sample only two good strings with minimum length exist: "_cfmailru_" and "_mailrucf_". The first string is lexicographically minimum.

字符串的某个子串被称为最频繁子串，当且仅当它的出现次数不小于任何其他子串的出现次数。给你一个字符串集合。一个字符串（不一定来自该集合）被称为“好”的，当且仅当该集合中的所有字符串都是这个字符串的最频繁子串。请找出长度最小的非空好字符串。如果存在多个这样的字符串，请输出字典序最小的那个。如果不存在好字符串，请输出 "_NO_"（不含引号）。字符串的子串是指该字符串中连续的字母序列。例如，"_ab_"、"_c_"、"_abc_" 都是字符串 "_abc_" 的子串，而 "_ac_" 不是。一个子串在字符串中的出现次数，是指该子串在字符串中作为连续子序列出现的起始位置的数量。这些出现可以重叠。字符串 #cf_span[a] 字典序小于字符串 #cf_span[b]，当且仅当 #cf_span[a] 是 #cf_span[b] 的前缀，或者在 #cf_span[a] 和 #cf_span[b] 第一个不同的位置上，#cf_span[a] 的字母更小。第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）— 集合中字符串的个数。接下来的 #cf_span[n] 行，每行包含一个由小写英文字母组成的非空字符串。保证这些字符串互不相同。所有字符串的总长度不超过 #cf_span[105]。请输出长度最小的非空好字符串。如果存在多个这样的字符串，请输出其中字典序最小的。如果不存在好字符串，请输出 "_NO_"（不含引号）。可以证明，在第一个样例中，仅有两个长度最小的好字符串："_cfmailru_" 和 "_mailrucf_"。其中第一个字符串字典序更小。 ## Input 第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）— 集合中字符串的个数。接下来的 #cf_span[n] 行，每行包含一个由小写英文字母组成的非空字符串。保证这些字符串互不相同。所有字符串的总长度不超过 #cf_span[105]。 ## Output 请输出长度最小的非空好字符串。如果存在多个这样的字符串，请输出其中字典序最小的。如果不存在好字符串，请输出 "_NO_"（不含引号）。 [samples] ## Note 可以证明，在第一个样例中，仅有两个长度最小的好字符串："_cfmailru_" 和 "_mailrucf_"。其中第一个字符串字典序更小。

Given a finite set $ S = \{s_1, s_2, \dots, s_n\} $ of distinct non-empty strings over the alphabet $ \Sigma = \{a, b, \dots, z\} $, with total length $ \sum_{i=1}^n |s_i| \leq 10^5 $, find the lexicographically smallest non-empty string $ T \in \Sigma^* $ such that: - Every string $ s_i \in S $ is a **most frequent substring** of $ T $, i.e., for all $ s_i, s_j \in S $, the number of occurrences of $ s_i $ in $ T $ equals the number of occurrences of $ s_j $ in $ T $, and this common value is at least as large as the number of occurrences of any other substring $ u \notin S $ in $ T $. If no such $ T $ exists, output `_NO_`. --- **Formal Constraints:** Let $ \text{occ}(u, T) $ denote the number of (overlapping) occurrences of substring $ u $ in string $ T $. Define: - $ M = \max_{u \in \Sigma^*} \text{occ}(u, T) $ - $ F(T) = \{ u \in \Sigma^* \mid \text{occ}(u, T) = M \} $ Then $ T $ is **good** if and only if: $$ F(T) = S $$ We seek the lexicographically smallest $ T \in \Sigma^+ $ of minimum possible length satisfying the above. If no such $ T $ exists, output `_NO_`.

Samples

Input #1

4
mail
ai
lru
cf

Output #1

cfmailru

Input #2

3
kek
preceq
cheburek

Output #2

NO

API Response (JSON)

{
  "problem": {
    "name": "D. Restoration of string",
    "description": {
      "content": "A substring of some string is called the most frequent, if the number of its occurrences is not less than number of occurrences of any other substring. You are given a set of strings. A string (not n",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF890D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A substring of some string is called the most frequent, if the number of its occurrences is not less than number of occurrences of any other substring.\n\nYou are given a set of strings. A string (not n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "字符串的某个子串被称为最频繁子串，当且仅当它的出现次数不小于任何其他子串的出现次数。\n\n给你一个字符串集合。一个字符串（不一定来自该集合）被称为“好”的，当且仅当该集合中的所有字符串都是这个字符串的最频繁子串。请找出长度最小的非空好字符串。如果存在多个这样的字符串，请输出字典序最小的那个。如果不存在好字符串，请输出 \"_NO_\"（不含引号）。\n\n字符串的子串是指该字符串中连续的字母序列。例如，\"_...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given a finite set $ S = \\{s_1, s_2, \\dots, s_n\\} $ of distinct non-empty strings over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $, with total length $ \\sum_{i=1}^n |s_i| \\leq 10^5 $, find the lexico...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments