如何修改代码找出字符串中所有匹配的列表元素？及高效方案问询

问题描述 #

现有如下字符串和列表：

my_string = "one two three"
my_list = ["one", "two", "three", "four"]

需求是找出my_string中所有存在于my_list的子字符串。

尝试了以下代码：

matches = []

if any((match := sub_string) in my_string for sub_string in my_list):
   matches.append(match)

执行后打印matches得到结果：["one"]，但预期结果是["one", "two", "three"]——代码找到第一个匹配项后就终止了后续查找。

提出两个问题：

1. 如何修改代码以实现需求？
2. 是否存在更高效的实现方式？

问题解答 #

1. 修改代码实现需求 #

any()函数的特性是只要迭代器中出现第一个True值就会停止遍历，所以只能拿到第一个匹配项。要收集所有符合条件的子字符串，直接遍历整个my_list并逐个判断即可：

基础循环写法

matches = []
for sub_string in my_list:
    if sub_string in my_string:
        matches.append(sub_string)

简洁列表推导式写法

matches = [sub for sub in my_list if sub in my_string]

两种写法都会完整遍历my_list，收集所有存在于my_string中的子字符串，执行后即可得到预期结果。

2. 更高效的实现方式 #

上面的原生写法时间复杂度为O(n*m)（n是my_list长度，m是my_string长度），当数据量较大时效率会降低。可以根据需求场景优化：

场景1：仅匹配空格分隔的单词

如果你的需求是匹配my_string中以空格分隔的完整单词（如示例中的情况），可以先将my_string分割为单词集合，利用集合O(1)的查找效率优化：

# 先将字符串转为单词集合
string_word_set = set(my_string.split())
# 保持原列表顺序的匹配结果
matches = [sub for sub in my_list if sub in string_word_set]

这种方式的时间复杂度降为O(n + m)，比原生写法高效得多。

场景2：匹配任意子字符串

如果需要匹配任意位置的子字符串（而非仅空格分隔的单词），当my_list规模较大时，推荐使用Aho-Corasick自动机算法——只需遍历一次my_string就能找出所有匹配的子字符串。Python中可以通过第三方库pyahocorasick实现，示例代码如下：

import ahocorasick

# 构建自动机
automaton = ahocorasick.Automaton()
for idx, sub in enumerate(my_list):
    automaton.add_word(sub, (idx, sub))
automaton.make_automaton()

# 查找所有匹配项
matches = set()
for end_idx, (idx, sub) in automaton.iter(my_string):
    matches.add(sub)
# 转回列表（如需保持原顺序可调整）
matches = [sub for sub in my_list if sub in matches]

这种方式的时间复杂度为O(m + k)，其中k是所有匹配项的数量，适合大规模子字符串匹配场景。

内容的提问来源于stack exchange，提问作者john_mon