如何高效筛选列表中与带通配符字符串匹配的子串？

给定带通配符?（代表任意单个字符）的字符串 s = "b?gb?rd"，以及字符串列表 l = ["big", "gg", "bird", "dra"]，需要从列表中筛选出所有能与s的某个子串匹配的元素（匹配规则：子串对应位置为?或与列表元素字符相同）。示例预期输出为 ["big", "bird", "gg"]。

此前的朴素实现时间复杂度约为O(n²)，以下提供两种更高效的解决方案：

方案一：KMP变种算法（适合列表元素数量适中的场景） #

核心思路 #

对列表中的每个字符串t，将其作为模式串，在原字符串s上执行带通配符的KMP匹配：

1. 若t的长度大于s的长度，直接跳过（不可能匹配）。
2. 为t构建KMP算法的失败函数（部分匹配表），用于匹配过程中的快速回退。
3. 遍历s，同时维护模式串的匹配位置：
   • 当s[i] == '?'或s[i] == t[j]时，匹配位置j向前推进。
   • 若j达到t的长度，说明找到匹配子串，将t加入结果集。
   • 若不匹配，根据失败函数将j回退到合适位置，继续匹配。

复杂度分析 #

单个模式串匹配时间为O(len(s) + len(t))，总时间复杂度为O(M*(len(s)+avg_len(t)))，其中M为列表元素数量，avg_len(t)为列表元素的平均长度，相比朴素的O(M*len(s)*avg_len(t))有明显提升。

代码示例（Python） #

def build_failure(pattern):
    n = len(pattern)
    fail = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and pattern[i] != pattern[j]:
            j = fail[j-1]
        if pattern[i] == pattern[j]:
            j += 1
            fail[i] = j
    return fail

def kmp_match(s, pattern):
    fail = build_failure(pattern)
    n, m = len(s), len(pattern)
    if m > n:
        return False
    j = 0
    for i in range(n):
        while j > 0 and s[i] != '?' and s[i] != pattern[j]:
            j = fail[j-1]
        if s[i] == '?' or s[i] == pattern[j]:
            j += 1
        if j == m:
            return True
    return False

s = "b?gb?rd"
l = ["big", "gg", "bird", "dra"]
result = [t for t in l if kmp_match(s, t)]
print(result)  # 输出: ['big', 'gg', 'bird']

方案二：AC自动机（适合列表元素数量庞大的场景） #

核心思路 #

将列表中所有字符串作为模式串构建AC自动机，然后遍历原字符串s，利用自动机的状态转移快速检测所有匹配的模式串：

1. 构建AC自动机的字典树（Trie），每个节点存储子节点链接、失败指针和匹配的模式串标记。
2. 预处理自动机的失败指针（类似KMP的失败函数，用于匹配失败时的状态回退）。
3. 遍历s的每个字符：
   • 若当前字符是?，则遍历当前状态的所有子节点，继续后续匹配；同时沿着失败指针收集所有匹配的模式串。
   • 若当前字符是普通字符，则转移到对应子节点（或通过失败指针回退），收集匹配的模式串。
4. 最后去重得到所有匹配的列表元素。

复杂度分析 #

构建自动机的时间为O(total_len(t))（total_len(t)为所有模式串的长度之和），遍历s的时间为O(len(s)*C)（C为字符集大小，此处为26个英文字母），总时间复杂度远低于朴素方案，适合处理大规模列表。

补充说明 #

如果列表中存在大量重复长度的字符串，还可以先按长度分组，对每个长度的子串批量处理，进一步优化效率。

内容的提问来源于stack exchange，提问作者Michael Angelo Hernandez