B. Restoration of string

Codeforces

IDCF889B

Time2000ms

Memory256MB

Difficulty—

dsugraphsstrings

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_"。其中第一个字符串字典序最小。

Let $ S = \{s_1, s_2, \dots, s_n\} $ be a set of $ n $ distinct non-empty strings over the alphabet $ \Sigma = \{a, b, \dots, z\} $, with total length $ \sum_{i=1}^n |s_i| \leq 10^5 $. Define: - For any string $ t $, let $ \text{occ}(t, u) $ denote the number of (overlapping) occurrences of substring $ t $ in string $ u $. - A substring $ t $ of $ u $ is *most frequent* in $ u $ if $ \text{occ}(t, u) \geq \text{occ}(t', u) $ for all substrings $ t' $ of $ u $. - A string $ u $ is *good* if every $ s_i \in S $ is a most frequent substring of $ u $, and no other substring has strictly more occurrences than the $ s_i $'s. Objective: Find the lexicographically minimum non-empty string $ u $ such that: 1. $ \forall s_i \in S $, $ \text{occ}(s_i, u) = M $, where $ M = \max_{t \subseteq u} \text{occ}(t, u) $, 2. $ |u| $ is minimized, 3. Among all such minimal-length strings, choose the lexicographically smallest. If no such $ u $ exists, output "_NO_". Constraints: - $ 1 \leq n \leq 10^5 $ - Each $ s_i \in \Sigma^+ $, all distinct - $ \sum_{i=1}^n |s_i| \leq 10^5 $ Note: All substrings are contiguous and occurrences may overlap.

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": "B. 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": "CF889B"
  },
  "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": "Let $ S = \\{s_1, s_2, \\dots, s_n\\} $ be a set of $ n $ distinct non-empty strings over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $, with total length $ \\sum_{i=1}^n |s_i| \\leq 10^5 $.\n\nDefine:\n- For ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments