c++ - 给定 1000 个长度为 100 的字符串，找出最小的唯一子字符串的长度

Question

给定 1000 个长度为 100 个字符的字符串。任务是计算每个字符串的最小子字符串长度，该长度在1000个字符串生成的所有子字符串中是唯一的。

我的方法

1. 为每个字符串生成长度为1-100的所有子字符串并将其存储在map中，如果发现重复的子字符串则继续增加计数。

2. 从长度为1的每个字符串重新生成所有子串，如果任意一个长度为L的子串的个数为1，则输出L。

观察

1. 此解决方案在 C++ 中获取 TLE，并在 java 中传递。我的理解是，STL::map 操作在 log(N) 时间内完成，而 HashMap 操作在 O(1) 内完成。

问题

• 我正在考虑一个解决方案，实现我自己的散列。我面临的问题是 1) 选择适合散列数组大小的值 2) 我如何从给定的字符串生成散列，以便碰撞可以最多避免。

上述问题的任何其他最佳方法都是可取的。

Answer 1

1. 创建 char* 数组，每个元素都是指向字符串中每个符号的指针。对于您的问题，数组大小为 100x1000 = 100000 个 char* 指针。 O(N)

2. 将此数组排序为“按字母顺序排列的字符串”。 O(N*Log(N))

3. 扫描字符串，并为每个 [i]-th 字符串搜索 max_eq_prefix 在这个字符串和字符串 [i+1] 和 [i-1] 之间。 对于第一个和最后一个字符串运行单次比较，使用 [i+1] 首先，[i-1] 最后。 O(N)

具有最小 max_eq_prefix 的字符串是您的子字符串， 长度为长度(max_eq_prefix) + 1。

计算 max_eq_prefix 的示例:

i-1:aabala
i:  aabumba
i+1:acron

对于字符串 [i]，max_eq_prefix 是 aab。所以，唯一的子字符串是“aabu”。

如您所见，这是一种极小极大算法。