问题

给定 N 个长度为 M 的字符串，每次等概率随机抽取一个，问至少知道前多少位可以确定字符串是哪一个。

思考

对于每个字符串，当知道它和其他所有串的最大的LCP+1位时可以确定。

题解

做法一： 对于每个字符串枚举其他所有字符串算LCP取最大值。时间复杂度$O(n^{2}m)O(n^2m)$

做法二： 按字典序排序后，LCP只需要算相邻的两个。时间复杂度 $O(nmlogn)O(nmlog\; n)$

做法三： 建trie树后直接算和其他串的LCP。时间复杂度$O(nm)O(nm)$

吐槽

这题被改了一万个版本，下调了一万次难度，有一万种方法能通过此题。

Dengsh同学看着我拿着D的一血气球进了他监考的考场，他兴奋的蹦了起来（不是