<分区>
我有一个字符串和唯一子字符串列表。问题是识别我们的字符串中出现了哪些子字符串。
只需使用 2 个嵌套循环即可完成。
result = []
substrings = ['foo', 'bar', 'spam', 'eggs']
text = 'foo123123spameggsabcde'
for s in substrings:
if s in text:
result.append(s)
但它很慢，尤其是长字符串和许多子字符串。有没有办法更有效地执行此操作？
最佳答案
使用 SomeDude's algorithm来自 this similar question , 以下应该非常有效地工作:
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和子串中的common item，这就是问题的答案。
关于python - 是否有可能在一次迭代中或比 O(n*m) 更快地找到字符串中的指定子字符串？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/64215180/