假设我有一个字符串和一个字符串列表：
a = 'ABCDEFG'
b = ['ABC', 'QRS', 'AHQ']
如何提取列表 b 中与字符串 a 的一部分完全匹配的字符串？所以会返回就像['ABC']
最重要的问题是我有几千万的字符串，所以时间效率是必不可少的。
问问题
2133 次
5 回答
4
如果您只想要 b 中的第一个匹配项：
next((s for s in b if s in a), None)
这具有在找到匹配项后立即短路的优点，而其他列表解决方案将继续运行。如果没有找到匹配项，它将返回None。
于 2013-01-17T22:14:13.503 回答
1
请记住，Python 的子字符串搜索x in a已经针对一般情况进行了很好的优化（并且用 C 编码，用于 CPython），因此一般情况下您不太可能击败它，尤其是使用纯 Python 代码。
但是，如果您有更专业的案例，则可以做得更好。
例如，如果您有一个包含数百万个字符串的任意列表b，所有这些字符串都需要在一个a永远不会改变的巨大静态字符串中进行搜索，那么预处理a可以产生巨大的影响。（请注意，这与通常情况相反，其中预处理模式是关键。）
另一方面，如果您预计匹配的可能性不大，并且您已经b提前获得了整个列表，那么通过b某种方式组织您可能会获得一些巨大的收益。例如，"ABCD"如果"ABC"已经失败，则搜索没有意义；如果你需要同时搜索"ABC"，"ABD"你可以"AB"先搜索，然后检查它是否在后面，"C"所以"D"你不必重复自己；等等（甚至可以将所有内容合并b到一个足够接近最佳值的单个正则表达式中……尽管有数百万个元素，但这可能不是答案。）
但是很难提前猜测，没有比你给我们更多的信息，你想要什么算法。
维基百科对字符串搜索算法有很好的高级概述。还有一个专门用于一般模式匹配的网站，这似乎有点过时了，但我怀疑你是否会需要在过去 3 年中发明的算法。
于 2013-01-17T22:19:19.560 回答
0
回答：
(x for x in b if x in a )
这将返回一个生成器，该生成器将是匹配的列表。采取第一个或循环它。
于 2013-01-17T22:10:16.350 回答
0
于 2013-01-17T22:42:51.163 回答
0
In [3]: [s for s in b if s in a]
Out[3]: ['ABC']
b在我的机器上，当包含 20,000,000 个元素（测试a并b包含与问题中的字符串类似的字符串）时，这大约需要 3 秒。
于 2013-01-17T22:10:29.173 回答