B. Similar Words

Codeforces

IDCF856B

Time2000ms

Memory512MB

Difficulty—

dphashingstringstrees

English · Original

Chinese · Translation

Formal · Original

Let us call a non-empty sequence of lowercase English letters a word. Prefix of a word _x_ is a word _y_ that can be obtained from _x_ by removing zero or more last letters of _x_. Let us call two words similar, if one of them can be obtained from the other by removing its first letter. You are given a set _S_ of words. Find the maximal possible size of set of non-empty words _X_ such that they satisfy the following: * each word of _X_ is prefix of some word from _S_; * _X_ has no similar words. ## Input Input data contains multiple test cases. The first line of the input data contains an integer _t_ — the number of test cases. The descriptions of test cases follow. The first line of each description contains an integer _n_ — the number of words in the set _S_ (1 ≤ _n_ ≤ 106). Each of the following _n_ lines contains one non-empty word — elements of _S_. All words in _S_ are different. It is guaranteed that the total length of all words in one input data doesn't exceed 106. ## Output For each test case print one line that contains one integer _m_ — the maximal number of words that _X_ can contain. [samples]

我们称一个由小写英文字母组成的非空序列为一个 #cf_span(class=[tex-font-style-underline], body=[word])。单词 #cf_span[x] 的 #cf_span(class=[tex-font-style-underline], body=[Prefix]) 是一个可以通过从 #cf_span[x] 的末尾删除零个或多个字母得到的单词 #cf_span[y]。我们称两个单词 #cf_span(class=[tex-font-style-underline], body=[similar])，如果其中一个可以通过删除另一个的首字母得到。给定一个单词集合 #cf_span[S]。请找出一个非空单词集合 #cf_span[X] 的最大可能大小，使得它们满足以下条件：输入数据包含多个测试用例。输入的第一行包含一个整数 #cf_span[t] —— 测试用例的数量。接下来是各个测试用例的描述。每个测试用例描述的第一行包含一个整数 #cf_span[n] —— 集合 #cf_span[S] 中单词的数量（#cf_span[1 ≤ n ≤ 106]）。接下来的 #cf_span[n] 行每行包含一个非空单词 —— #cf_span[S] 的元素。#cf_span[S] 中的所有单词互不相同。保证单个输入数据中所有单词的总长度不超过 #cf_span[106]。对于每个测试用例，输出一行，包含一个整数 #cf_span[m] —— #cf_span[X] 最多可以包含的单词数量。 ## Input 输入数据包含多个测试用例。输入的第一行包含一个整数 #cf_span[t] —— 测试用例的数量。接下来是各个测试用例的描述。每个测试用例描述的第一行包含一个整数 #cf_span[n] —— 集合 #cf_span[S] 中单词的数量（#cf_span[1 ≤ n ≤ 106]）。接下来的 #cf_span[n] 行每行包含一个非空单词 —— #cf_span[S] 的元素。#cf_span[S] 中的所有单词互不相同。保证单个输入数据中所有单词的总长度不超过 #cf_span[106]。 ## Output 对于每个测试用例，输出一行，包含一个整数 #cf_span[m] —— #cf_span[X] 最多可以包含的单词数量。 [samples]

Let $ S $ be a finite set of non-empty strings over the lowercase English alphabet. Define a relation $ \sim $ on strings: $ x \sim y $ if one can be obtained from the other by removing the first character (i.e., $ x = ay $ or $ y = ax $ for some character $ a $). Let $ \mathcal{P} $ be the set of all prefixes of strings in $ S $, including the strings themselves. We seek the maximum size of a subset $ X \subseteq \mathcal{P} $ such that no two distinct elements in $ X $ are related by $ \sim $. That is, find the largest subset $ X \subseteq \mathcal{P} $ such that for all $ u, v \in X $ with $ u \ne v $, it is not the case that $ u \sim v $. Equivalently: Maximize $ |X| $ subject to $ \forall u, v \in X, u \ne v \Rightarrow u \not\sim v $.

Samples

Input #1

2
3
aba
baba
aaab
2
aa
a

Output #1

6
1

API Response (JSON)

{
  "problem": {
    "name": "B. Similar Words",
    "description": {
      "content": "Let us call a non-empty sequence of lowercase English letters a word. Prefix of a word _x_ is a word _y_ that can be obtained from _x_ by removing zero or more last letters of _x_. Let us call two wo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF856B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let us call a non-empty sequence of lowercase English letters a word. Prefix of a word _x_ is a word _y_ that can be obtained from _x_ by removing zero or more last letters of _x_.\n\nLet us call two wo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "我们称一个由小写英文字母组成的非空序列为一个 #cf_span(class=[tex-font-style-underline], body=[word])。单词 #cf_span[x] 的 #cf_span(class=[tex-font-style-underline], body=[Prefix]) 是一个可以通过从 #cf_span[x] 的末尾删除零个或多个字母得到的单词 #cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ S $ be a finite set of non-empty strings over the lowercase English alphabet.\n\nDefine a relation $ \\sim $ on strings: $ x \\sim y $ if one can be obtained from the other by removing the first cha...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments