首页 > 试题广场 >

假的字符串

[编程题]假的字符串

给定n个字符串，互不相等，你可以任意指定字符之间的大小关系（即重定义字典序），求有多少个串可能成为字典序最小的串，并输出它们

第一行一个数表示n
之后n行每行一个字符串表示给定的字符串

第一行输出一个数x表示可行的字符串个数
之后输出x行，每行输出一个可行的字符串
输出的顺序和输入的顺序一致

示例1

输入

6
mcfx
ak
ioi
wen
l
a

5
mcfx
ioi
wen
l
a

对于100%的数据，
n <= 30000 , 字符串总长<= 300000
字符集为小写字符

算法知识视频讲解

小布小布

发表于 2022-12-11 00:20:00

首先判断一下这个串是不是某个串的前缀像s1 = ab 与 s2 =abb ,这里s1是s2的前缀，那么s2就一定不可以判断一下优先级是否合法， s1=ab, s2=bb, s3=aa s1是一定不可以作为开头的，比较s1和s2的时候a>b,比较s1和s3的时候a<b 也就是自相矛盾展开全文

字典树（Trie树）

上传者：牛客301599号

难度：

0条回答 0收藏 757浏览

查看代码

假的字符串

扫一扫，把题目装进口袋