#P3065. [USACO12DEC] First! G

    ID: 3893 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>字符串2012USACO哈希 hashing字典树 Trie

[USACO12DEC] First! G

题目描述

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

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

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

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

输入格式

11 行:一个数字 NN1N30,0001\le N \le 30,000),表示 Bessie 正在研究字符串的数量。

2N+12\sim N+1 行:每行包含一个非空字符串。所有字符串包含的字符总数不会超过 300,000300,000。输入中的所有字符都是小写字母,即 aza\sim z。输入不包含重复的字符串。

输出格式

11 行:一个数字 KK,表示按重排的字母表顺序排列后可以排在第一个的字符串数量。

2K+12\sim K+1 行:第 i+1i+1 行包含第 ii 个按重排的字母表顺序排列后可以排在第一个的字符串。字符串应该按照它们在输入中的顺序来输出。

4
omm
moo
mom
ommnom

2
omm
mom

提示

样例即题目描述中给出的例子,只有 omm\texttt{omm}mom\texttt{mom} 在各自特定的字典序下可以被排列在第一个。