是否有可能在一次迭代中找到字符串中指定的子字符串，或者比O（n*m）更快？

Question

我有一个字符串和唯一的子字符串列表。问题在于识别字符串中出现的子字符串

只需使用2个嵌套循环即可完成

result = []
substrings = ['foo', 'bar', 'spam', 'eggs']
text = 'foo123123spameggsabcde'

for s in substrings:
    if s in text:
        result.append(s)

但是它很慢，特别是长字符串和许多子字符串。有没有办法更有效地执行此操作

Answer 1

使用来自this similar question的SomeDude's algorithm， 以下各项应能非常有效地发挥作用：

lens=set([len(i) for i in substrings])
d={}
for k in lens:
    d[k]=[text[i:i+k] for i in range(len(text)-k)]
s=set(sum(d.values(), []))
result=list(s.intersection(set(substrings)))

print(result)

['foo', 'spam', 'eggs']

说明： 我们将所有可能长度的单词保存在子字符串中。对于这些长度，我们在文本（集合s）中创建了所有可能的子字符串。最后，我们在s和子字符串中找到了公共项，这就是问题的答案