python - 寻找最短的唯一子串

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"

我可以很容易地强制执行此操作，方法是获取所选名称的第一个字母并查看它是否与任何名称匹配，然后遍历其余字母，然后是成对的字母，等等。

我的问题是我的列表包含一万多个名字，而且它们相当长 - 更类似于书名。蛮力将永远持续下去。

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

标签： python

Answer 1

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

使用上面的 Wikipedia 文章作为参考：您可以按时间构建树O(n)（所有字符串，而不是单个字符串），并使用它来及时查找长度z字符串的所有出现。实施得当，您可能会在某个时间查看单词列表（欢迎任何人仔细检查我的数学）。PmO(m + z)O(n) + O(am + az) = O(am + az)a