{"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 words similar, if one of them can be obtained from the other by removing its first letter.\n\nYou 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:\n\n*   each word of _X_ is prefix of some word from _S_;\n*   _X_ has no similar words.\n\n## Input\n\nInput 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.\n\nThe 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.\n\nIt is guaranteed that the total length of all words in one input data doesn't exceed 106.\n\n## Output\n\nFor each test case print one line that contains one integer _m_ — the maximal number of words that _X_ can contain.\n\n[samples]","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_span[y]。\n\n我们称两个单词 #cf_span(class=[tex-font-style-underline], body=[similar])，如果其中一个可以通过删除另一个的首字母得到。\n\n给定一个单词集合 #cf_span[S]。请找出一个非空单词集合 #cf_span[X] 的最大可能大小，使得它们满足以下条件：\n\n输入数据包含多个测试用例。输入的第一行包含一个整数 #cf_span[t] —— 测试用例的数量。接下来是各个测试用例的描述。\n\n每个测试用例描述的第一行包含一个整数 #cf_span[n] —— 集合 #cf_span[S] 中单词的数量（#cf_span[1 ≤ n ≤ 106]）。接下来的 #cf_span[n] 行每行包含一个非空单词 —— #cf_span[S] 的元素。#cf_span[S] 中的所有单词互不相同。\n\n保证单个输入数据中所有单词的总长度不超过 #cf_span[106]。\n\n对于每个测试用例，输出一行，包含一个整数 #cf_span[m] —— #cf_span[X] 最多可以包含的单词数量。\n\n## Input\n\n输入数据包含多个测试用例。输入的第一行包含一个整数 #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]。\n\n## Output\n\n对于每个测试用例，输出一行，包含一个整数 #cf_span[m] —— #cf_span[X] 最多可以包含的单词数量。\n\n[samples]","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 character (i.e., $ x = ay $ or $ y = ax $ for some character $ a $).\n\nLet $ \\mathcal{P} $ be the set of all prefixes of strings in $ S $, including the strings themselves.\n\nWe seek the maximum size of a subset $ X \\subseteq \\mathcal{P} $ such that no two distinct elements in $ X $ are related by $ \\sim $.\n\nThat 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 $.\n\nEquivalently: Maximize $ |X| $ subject to $ \\forall u, v \\in X, u \\ne v \\Rightarrow u \\not\\sim v $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF856B","tags":["dp","hashing","strings","trees"],"sample_group":[["2\n3\naba\nbaba\naaab\n2\naa\na","6\n1"]],"created_at":"2026-03-03 11:00:39"}}