Python实现：检查字符串是否含最多1个字符差异的子串

我有一个包含数千个字符串的列表sub_strings，还有一个包含数百万个字符串的列表strings。需要检查strings中的每个元素是否包含sub_strings中的任意子串，或是包含与该子串仅有1个字符差异的子串。

示例代码：

sub_strings = ['hello']
strings =     ['hell dude whats good',
               'hllo',
               'hallo',
               'hello',
               'dude whats good']

is_substring_no_more_then_1_differnce(strings , sub_strings)

预期输出：

[True, True, True, True, False]

解决方案 #

核心思路 #

由于数据规模庞大（百万级strings+数千级sub_strings），暴力遍历匹配的效率完全无法接受。这里推荐两种高效思路：

1. n-gram索引预处理 + 编辑距离验证

• 预处理阶段：对每个子串生成所有n-gram（比如取n=3），构建倒排索引（键为n-gram，值为对应子串集合）。这样能快速筛选出与当前字符串片段可能存在1个字符差异的候选子串，避免无意义的编辑距离计算。
• 匹配阶段：对每个目标字符串生成所有n-gram，查索引得到候选子串，再在对应位置滑动窗口计算编辑距离，判断是否≤1。

2. 扩展Aho-Corasick自动机

基于多模式匹配的Aho-Corasick自动机，扩展支持1次插入/删除/替换操作的路径，能在O(L)时间（L为目标字符串长度）内完成匹配，适合大规模数据处理。

基础验证代码（小规模场景） #

如果先需要验证逻辑正确性，可使用以下简化实现：

def is_substring_no_more_than_1_difference(strings, sub_strings):
    def edit_distance_at_most_1(s1, s2):
        len1, len2 = len(s1), len(s2)
        if abs(len1 - len2) > 1:
            return False
        
        diff_count = 0
        i = j = 0
        while i < len1 and j < len2:
            if s1[i] != s2[j]:
                diff_count += 1
                if diff_count > 1:
                    return False
                # 处理长度不一致的情况（插入/删除）
                if len1 > len2:
                    i += 1
                elif len2 > len1:
                    j += 1
                else:
                    i += 1
                    j += 1
            else:
                i += 1
                j += 1
        # 剩余未匹配的字符也算差异
        diff_count += (len1 - i) + (len2 - j)
        return diff_count <= 1

    # 按长度分组子串，减少遍历次数
    sub_groups = {}
    for sub in sub_strings:
        l = len(sub)
        if l not in sub_groups:
            sub_groups[l] = []
        sub_groups[l].append(sub)
    
    result = []
    for s in strings:
        found = False
        s_len = len(s)
        # 遍历所有可能的子串长度（原长度或±1）
        for sub_len in sub_groups:
            # 目标字符串长度过小，直接跳过
            if s_len < sub_len - 1:
                continue
            # 滑动窗口匹配同长度子串
            if s_len >= sub_len:
                for i in range(s_len - sub_len + 1):
                    window = s[i:i+sub_len]
                    for sub in sub_groups[sub_len]:
                        if edit_distance_at_most_1(window, sub):
                            found = True
                            break
                    if found:
                        break
            # 处理子串比目标字符串长1的情况（目标字符串是子串删除一个字符的结果）
            if not found and sub_len == s_len + 1:
                for sub in sub_groups[sub_len]:
                    if edit_distance_at_most_1(s, sub):
                        found = True
                        break
            if found:
                break
        result.append(found)
    return result

# 测试示例
sub_strings = ['hello']
strings =     ['hell dude whats good',
               'hllo',
               'hallo',
               'hello',
               'dude whats good']
print(is_substring_no_more_than_1_difference(strings, sub_strings))

性能优化建议 #

1. n-gram索引优化：用n-gram提前筛选候选子串，将编辑距离计算的次数从数千级降到个位数。
2. 使用C扩展库：用python-Levenshtein替代自定义编辑距离函数，速度提升10~100倍。
3. 并行处理：对百万级strings采用多进程/多线程拆分任务，充分利用CPU资源。
4. 自动机实现：若数据规模极大，可基于Aho-Corasick自动机扩展实现1编辑距离匹配，性能最优。

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