寻找最短唯一子串

Question

我有一个名字和一组名字列表。我可以保证所选的名字包含在其他名称列表中。

我想生成所选名称的最短子字符串，该子字符串仅由该名称包含，而不由数据中任何其他名称包含。

>>> names = ['smith','jones','williams','brown','wilson','taylor','johnson','white','martin','anderson']
>>> find_substring('smith', names)
"sm"
>>> find_substring('williams', names)
"ll"
>>> find_substring('taylor', names)
"y"

我可以很容易地使用暴力破解方法，通过取选定名称的第一个字母并查看它是否与任何名称匹配，然后迭代遍历其余字母后跟一对字母等。

但我的问题是，我的列表包含超过一万个名称，并且它们相当长——更类似于书名。暴力破解需要非常长的时间。

有没有一些简单的方法可以高效地实现这一点？

- snazzybouche

---

你的意思是，你只需要做一次这个操作，还是需要对许多不同的名称进行操作，但是names列表是固定的？ - kaya3

我不确定你所说的暴力破解是什么意思，但我希望它不会花费太长时间，应该在一秒钟以内完成，而不是“永远”。 - Kelly Bundy

你可以尝试实现你的暴力算法，并进行基准测试，以确定它是否真的需要“永远”运行。如果确实如此，我们可以使用该基准测试来测试更好的解决方案。 - Kelly Bundy

我同意@HeapOverflow上述的所有观点（删除了旧评论并将它们作为答案添加在下面，以便独立讨论，如果OP感兴趣）。 - felipe

威廉姆斯也可能是IA。 - Derek Eden

Answer 1

一种常见后缀树的变体可能足以在不到O(n^2)的时间内实现此目标（用于大规模基因组测序的生物信息学中），但正如@HeapOverflow在评论中提到的那样，我认为暴力解决这个问题不会成为一个问题，除非您考虑使用数亿个字符串运行该算法。

使用上面的维基百科文章作为参考：您可以在O(n)的时间内（所有字符串，而不是单个字符串）构建树，并将其用于在O(m+z)的时间内查找长度为m的字符串P的所有z出现。如果正确实现，您可能会看到O(n)+O(am+az)=O(am+az)时间的列表a单词（欢迎任何人在此方面进行双重检查）。

- felipe

---

我看过 < 符号，但它并没有真正帮助理解。仍然不清楚 O(n^2) 的复杂度是从哪里来的。这与生物信息学中用于大基因组测序的复杂度有关吗？在这里扮演了什么角色，即为什么要提到它？O(n^2) 比我能想到的任何暴力算法都要糟糕得多。 - Kelly Bundy

从字符串中找到所有子字符串，暴力方法并确保顺序为O(n^2)。无论顺序如何找到所有子字符串的时间复杂度为O(2^n)（幂集）。在这种情况下，我假设OP是指确保顺序。 - felipe

没错，但那个字符串就像是所有名称的连接，对各个子串感兴趣的人都不正常吧？这有什么帮助呢？ - Kelly Bundy

Answer 2

我认为最好的方法是使用暴力破解，但需要记录已检查的字母组合以及它们是否匹配其他名称的字典。

["s":true, "m": true, "sm": false"]

首先查阅此列表可以减少检查其他字符串的代码，提高方法运行速度。

- user11114632