Python中如何忽略指定字符查找子串的所有出现位置？

需求说明 #

需要实现一个函数，在忽略指定字符的前提下，找出子串在长字符串中的所有出现位置，返回每个匹配的起始和结束索引（原字符串中的下标）。

示例代码 #

long_string = 'this is a t`es"t. Does the test work?'
small_string = "test"
chars_to_ignore = ['"', '`']
print(find_occurrences(long_string, small_string))

预期输出 #

[(10, 16), (27, 31)]

• (10, 16) 对应长字符串中的tes"t，忽略和"后正好是test
• (27, 31) 对应长字符串中的test

直接使用re.finditer的问题 #

直接用正则匹配无法满足需求，因为它只会匹配连续的目标子串，不会自动跳过指定忽略字符：

import re
long_string = 'this is a t`es"t. Does the test work?'
small_string = "test"
matches = []
[matches.append((m.start(), m.end())) for m in re.finditer(small_string, long_string)]
print(matches)

输出仅为[(27, 31)]，遗漏了第一个匹配项。

解决方案：双指针遍历法 #

通过双指针分别遍历长字符串和子串，遇到忽略字符时跳过，完成匹配后记录原字符串的索引：

def find_occurrences(long_str, small_str, chars_to_ignore):
    ignore_set = set(chars_to_ignore)
    small_length = len(small_str)
    long_length = len(long_str)
    occurrences = []

    for i in range(long_length):
        # 跳过起始位置的忽略字符
        if long_str[i] in ignore_set:
            continue
        
        long_ptr = i
        small_ptr = 0

        # 双指针匹配子串，跳过忽略字符
        while long_ptr < long_length and small_ptr < small_length:
            if long_str[long_ptr] in ignore_set:
                long_ptr += 1
                continue
            
            if long_str[long_ptr] == small_str[small_ptr]:
                long_ptr += 1
                small_ptr += 1
            else:
                break
        
        # 子串完全匹配时记录索引
        if small_ptr == small_length:
            occurrences.append((i, long_ptr))
    
    return occurrences

# 测试验证
long_string = 'this is a t`es"t. Does the test work?'
small_string = "test"
chars_to_ignore = ['"', '`']
print(find_occurrences(long_string, small_string, chars_to_ignore))

代码逻辑说明 #

1. 将忽略字符转为集合，提升查询效率
2. 遍历长字符串的每个位置，作为匹配的起始候选点，遇到忽略字符直接跳过
3. 用双指针分别遍历长字符串（long_ptr）和子串（small_ptr）：
   • 长指针遇到忽略字符时直接后移
   • 字符匹配成功时，两个指针同时后移
   • 字符不匹配时终止当前匹配尝试
4. 当子串指针走完整个子串，说明匹配成功，记录原字符串的起始索引i和结束索引long_ptr

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