列表搜索中的快速字符串

Question

使用Python 3,我有一个包含超过100,000个字符串(list1)的列表,每个字符串最多300个字符.我还有一个包含超过900万个子串的列表(list2) - 我想计算list2中子串的元素数量.例如,

list1 = ['cat', 'caa', 'doa', 'oat']
list2 = ['at', 'ca', 'do']

我希望函数返回(映射到list2):

[2, 2, 1]

通常,这非常简单,只需要很少.但是,由于列表的大小,我有效率问题.我想找到返回该计数器列表的最快方法.

我已经尝试过列表推导,生成器,地图,各种循环,我还没有找到一种快速的方法来完成这项简单的任务.理论上什么是完成这个目标的最快方法,最好O(len(list2))是快速采取措施？

Answer 1

设置M = len(list1)和N = len(list2)

对于 中的 N 个条目中的每一个，list2您都必须与 中的条目进行 M 次比较list1。这是最坏情况下的运行时间O(M x N)。如果你更进一步，让每个条目的list2长度为 1，每个条目的list1长度为 300，那么你得到的运行时间为O(300M x N)。

如果性能确实是一个问题，请尝试动态编程。这是一个开始：

1）list2按长度升序排序，如下所示：

['scorch', 'scorching', 'dump', 'dumpster', 'dumpsters']

2）将它们排序到子列表中，使得每个前面的条目都是后面的条目的子集，如下所示：

[['scorch', 'scorching'] , ['dump', 'dumpster', 'dumpsters']]

3）现在，如果您比较的list1和'scorch'不在那里，那么您就不必搜索其中'scorching'任何一个。同样，如果'dump'不在那里，则既不存在也不'dumpster'存在'dumpsters'

请注意，最坏​​情况下的运行时间仍然相同