/ Vijos / 题库 /

First!

First!

时间限制:1秒  内存限制:256M


【题目描述】

  Bessie一直在研究字符串。她发现,通过改变字母表的顺序,她可以按改变后的字母表来排列字符串(字典序大小排列)。

  例如,Bessie发现,对于字符串串“omm”,“moo”,“mom”和“ommnom”,她可以使用标准字母表使“mom”排在第一个(即字典序最小),她也可以使用字母表“abcdefghijklonmpqrstuvwxyz”使得“omm”排在第一个。然而,Bessie想不出任何方法(改变字母表顺序)使得“moo”或“ommnom”排在第一个。

  接下来让我们通过重新排列字母表的顺序来计算输入中有哪些字符串可以排在第一个(即字典序最小),从而帮助Bessie。

  要计算字符串 X 和字符串 Y 按照重新排列过的字母表顺序来排列的顺序,先找到它们第一个不同的字母 X[i] 与 Y[i],按重排后的字母表顺序比较,若 X[i] 比 Y[i] 先,则 X 的字典序比 Y 小,即 X 排在 Y 前;若没有不同的字母,则比较 X 与 Y 长度,若 X 比 Y 短,则 X 的字典序比 Y 小,即 X 排在 Y 前。

【输入格式】

  第 1 行:一个数字 \(N\),Bessie正在研究的字符串的数量。
  第 2~\(N+1\) 行:每行包含一个非空字符串。所有字符串包含的字符总数不会超过 300,000。 输入中的所有字符都是小写字母,即 a~z。 输入不包含重复的字符串。

【输出格式】

  第 1 行:一个数字K,表示按重排后的字母表顺序排列的字符串有多少可以排在第一个数量。
  第 2~\(K+1\) 行:第 \(i+1\) 行包含第 \(i\) 个按重排后的字母表顺序排列后可以排在第一个的字符串。字符串应该按照它们在输入中的顺序来输出。

【输入输出样例】

 Input

4 
omm 
moo 
mom 
ommnom

 Output

2 
omm 
mom 

【输入输出样例解释】

  样例即是题目描述中的例子,只有“omm”和“mom”在各自特定的字典序下可以被排列在第一个。

【数据限制】

  对于 \(100\%\) 的数据,\(1≤N≤30000\)。

【来源】

  Mr.he

信息

ID
2235
难度
(无)
分类
字符串 | Trie树图结构 | 拓扑排序 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
1
上传者