在不多次迭代的情况下在字符串中查找多个子字符串

Question

我需要查找列表中的项目是否出现在字符串中，然后将这些项目添加到不同的列表中。此代码有效：

data =[]
line = 'akhgvfalfhda.dhgfa.lidhfalihflaih**Thing1**aoufgyafkugafkjhafkjhflahfklh**Thing2**dlfkhalfhafli...'
_legal = ['thing1', 'thing2', 'thing3', 'thing4',...] 
for i in _legal:
    if i in line:
        data.append(i)

但是，代码迭代 line（可能很长）多次 - 与 _legal 中的项目（可能是 lot).这对我来说太慢了，我正在寻找一种更快的方法。 line 没有任何特定的格式，所以据我所知，使用 .split() 是行不通的。编辑：更改 line 以便更好地代表问题。

Answer 1

一种方法是构建一个非常简单的正则表达式模式，并使用 re.findall() 到 find/extract 字符串中任何匹配的词。

import re

line = 'akhgvfalfhda.dhgfa.lidhfalihflaih**Thing1**aoufgyafkugafkjhafkjhflahfklh**Thing2**dlfkhalfhafli...'
_legal = ['thing1', 'thing2', 'thing3', 'thing4']

exp = re.compile(r'|'.join(_legal), re.IGNORECASE)
exp.findall(line)

>>> ['Thing1', 'Thing2']

Answer 2

我能想到的一种改进方法是：

获取_legal
使用滑动 window 技术从这些特定长度的 line 构建单词词典。复杂度应该是O( len(line)*num_of_unique_lengths )，这应该比蛮力好。
现在在 O(1) 的字典中查找每个 thing。

代码：

line = 'thing1 thing2 456 xxualt542l lthin. dfjladjfj lauthina '
_legal = ['thing1', 'thing2', 'thing3', 'thing4', 't5', '5', 'fj la']
ul = {len(i) for i in _legal}
s=set()
for l in ul:
    s = s.union({line[i:i+l] for i in range(len(line)-l)})
print(s.intersection(set(_legal)))

输出：

{'thing1', 'fj la', 'thing2', 't5', '5'}

Answer 3

以下内容应该非常有效。它实现了

的建议

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

对于以下数据（由于 Thing1 和 Thing2 中的大写字母，它返回一个空列表，我稍微更改了“行”）

line = 'akhgvfalfhda.dhgfa.lidhfalihflaih**thing1**aoufgyafkugafkjhafkjhflahfklh**thing2**dlfkhalfhafli...'
_legal = ['thing1', 'thing2', 'thing3', 'thing4',...]

输出为：

print(result)

['thing2', 'thing1']

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

在不多次迭代的情况下在字符串中查找多个子字符串

Finding multiple substrings in a string without iterating over it multiple times

python

string

full-text-search