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

Question

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

我的方法

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

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* 指针。上）

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

3. 扫描字符串，并为每个第 [i] 个字符串搜索此字符串与字符串 [i+1] 和 [i-1] 之间的 max_eq_prefix。对于第一个和最后一个字符串，运行单个比较，第一个是 [i+1]，最后一个是 [i-1]。上）

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

计算 max_eq_prefix 的示例：

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

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

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