有个字符串, 每一次操作可以任意选择一个字符串T
.(可以为空串并且不一定是题目所给的字符串) 然后考虑所有还没有被删除的字符串S
, 如果T
是S
的一个前缀(空串是任意串的前缀), 那么把它加入候选删除集合.
但是每一次操作最多删除个字符串, 也就是说如果候选集合中字符串的数量大于, 那么什么也不会发生. 否则, 删除其中所有的字符串.
求出最少需要多少次操作才能删掉所有的字符串.
第一行输入两个正整数和. 如题意所示.
接下来行, 每一行输入一个仅包含小写英文字母的字符串.
数据保证没有两个相同的字符串.
对于所有数据 满足, , . (所有字符串的长度之和)
一行输出一个正整数, 表示最少需要多少次操作才能删除所有字符串.
4 2
a
abc
abd
b
2
我们可以第一次操作选择ab
. 删掉abc
和abd
.
第二次操作选择空串. 将剩下的所有字符串删掉.
4 2
d
c
ab
a
2
5 3
please
remove
all
these
files
3