Similar Words

题意翻译

【题目描述】 单词是由小写英文字母组成的非空串。 若一个单词去掉首字母后与另一个单词相同，则这两个单词相似。 现给定n个单词(可能重复)，请挑选尽量多的新单词组成集合x并满足条件： 1. 集合x中的新单词为原n个单词的前缀（包含自身） 2. 集合x中的新单词两两不相似。 输出x中的最大单词数。 共有t组数据 【输入格式】 第一行有1个整数t 接下来t个任务，每个任务第一行为单词数n 接下来n行每行表示一个单词 【输出格式】 t行表示t个任务的答案 【样例输入1】 2 3 aba baba aaab 2 aa a 【样例输出1】 6 1 【数据范围】 对于20%数据，1<=n<=20,长度之和不超过100 对于50%数据，1<=n<=5000 对于100%数据，1<=n<=1000000 数据保证在一组任务中的所有单词长度之和不超过1000000

题目描述

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 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<=10^{6} $ ). 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 $ 10^{6} $ .

输出格式

For each test case print one line that contains one integer $ m $ — the maximal number of words that $ X $ can contain.

输入输出样例

输入样例 #1

2
3
aba
baba
aaab
2
aa
a

输出样例 #1

6
1