#P2992. USACO(45)TRIE2:一号单词P3065 [USACO12DEC] First! G
USACO(45)TRIE2:一号单词P3065 [USACO12DEC] First! G
Description
【题意】日常生活中的英文字典在编排过程中,使用的是字典序。
字典序的规定空字符串是最小的;
对于非空字符串,取决于首字母的大小;
首字母相同的两个字符串,则大小取决于排除首字母的部分。
奶牛发现,如果重新定义英文字符的顺序,那么字典的顺序也会改变。
给定一本字典中的所有单词,假设奶牛可以任意指定英文字符的顺序,那么有哪些单词可能排在字典的第一名呢?
举例来说,假设有四个单词:omm,moo,mom 和 ommnom,如果奶牛定义 o 在 m 之前,则omm 可排第一,如果定义m在o之前,则mom可排第一,但余下两个单词是无论如何不可能排在
第一的。
【输入格式】
• 第一行:单个整数 $N,1≤N≤30000$
• 第二行到$N+1$行:每行一个字符串,表示字典中的一个单词,完全由小写字母构成,保证没有两个单词是完全一样的
• 所有单词的长度之和不超过$3 \times 10^5$
【输出格式】
• 第一行:单个整数$K$,表示有$K$个可以排在第一名的单词
• 第二行到$K+1$行:每行输出一个可以排在第一名的单词,表示这些单词的输出顺序必须和输入时一致
【样例输入】
4
omm
moo
mom
ommnom
【样例输出】
2
omm
mom