给你 n 个按照特殊字典序排好序的单词,你来设计一种字典序,使得按照你的这种字典序来排序这 n 个单词,得到的结果与给出的单词序列相同。如果做不到,请输出 Impossible。
我们默认空字符是字典序最小的,所以 a < aa(即一个单词不能排在它的真前缀之后)。
这里“字典序”由 26 个互不相同字母的一个排列定义:排列中靠前的字母比靠后的字母小。两个单词比较时,从左到右第一个不同的字符决定大小;若一个是另一个的前缀,则较短者更小。
第 1 行:1 个数 n(1 <= n <= 100)。
后面 n 行:每行一个单词,只包括 a-z 这 26 个小写字母,单词长度 L <= 100。
输出共 26 个字母,对应一个 a-z 的排列(表示你设计的字典序,从左到右字母依次增大)。如果不存在满足要求的字典序,输出 Impossible。
本题为特殊判题(SPJ):只要输出的排列确实能使给出的单词序列成为该字典序下的升序即判为正确;若判定无解而输出 Impossible,需确实不存在任何合法排列。
3 rivest shamir adleman
bcdefghijklmnopqrsatuvwxyz
实质是拓扑排序。对相邻两个单词 w[i], w[i+1]:找到从左起第一个不同的字符 c1=w[i][k]、c2=w[i+1][k],连一条有向边 c1->c2(表示 c1 应排在 c2 前);若两词前缀相同而 w[i] 更长(w[i+1] 是 w[i] 的真前缀),则矛盾、无解。对得到的字母约束图做拓扑排序:若存在环则输出 Impossible;否则输出一个包含全部 26 个字母的拓扑序(未被约束的字母可任意插入)。样例中约束为 r<s、s<a,按最小字母优先拓扑可得 bcdefghijklmnopqrsatuvwxyz。