代码之家 › 专栏 › 技术社区 › snazzybouche

寻找最短的唯一子串

python

snazzybouche · 技术社区 · 6 年前

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

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

>>> 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"

我的问题是,我的名单上有一万多个名字,而且它们相当长——与书名更为相似。野蛮的武力需要永远 .

是否有一些简单的方法可以有效地实现这一点?

0 回复 | 直到 6 年前

user11114632 user11114632 6 年前

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

首先查阅此列表将有助于减少检查其他字符串的代码,并加快方法的运行速度。

felipe 6 年前

变型 common suffix tree 可能足以在不到一年的时间内实现这一目标 O(n^2) 时间(在生物信息学中用于大规模基因组测序),但正如@HeapOverflow在评论中提到的,我不认为暴力强迫这个问题会成为一个很大的问题,除非你考虑用几亿个字符串运行算法。

参考上面的维基百科文章:您可以在 O(n) 时间(所有字符串,而不是单个字符串),并使用它查找所有 z 字符串的出现 P m 在里面 O(m + z) 时间实施正确,您可能会看到 O(n) + O(am + az) = O(am + az) a 单词(欢迎任何人再次检查我的数学)。

推荐文章

Google User · Django管理员在`list_display中未显示`creation_date`字段`

1 年前

user29747013 · 如何创建一个新的数据框架,其中包含原始数据框架中列的聚合列?

1 年前

ÎÎÎ½Î· ÎÎ®Î¹Î½Î¿Ï · Python lxml.html语法错误:使用lxml find时XPATH的谓词无效

1 年前

user29715306 · from_users=和chats=电视节目中的差异

1 年前

Redshoe · 当执行numpy.genfromtxt()时,python是否会读取文件的所有行?

1 年前

RASEL MAHMUD · 为什么以及如何在is_even()函数内的IF条件中递归X变量在满足0后递增?[副本]

1 年前

prayner · 更新嵌套字典包含列表中的项

1 年前

Bringo Jr · 我可以在O(n)中解决这个问题吗?

1 年前

Dave · 如何在for循环中修改列表值

1 年前

Shukurullox Komiljonov · 从记录中获得相互和解。使用SQL

1 年前