Python正则匹配拼接字符串后获取匹配项对应原token序号的方法

原有拼接字符串减少正则执行次数的思路完全可行，核心缺陷是拼接后丢失了字符位置与原列表元素的映射关系，不需要退回逐元素执行正则的高开销方案，只要提前构建位置偏移映射，配合finditer返回的匹配位置信息，一次正则扫描就能拿到所有需要的结果。

实现思路 #

• 预处理阶段遍历一次原列表，记录每个元素在拼接字符串中的起始偏移位置，因为拼接用的分隔符长度固定，可以直接累计计算每个元素对应的字符区间，整体开销极低
• 正则匹配阶段使用re.finditer替代re.findall，该方法会逐次返回匹配对象，可直接获取每个匹配项的内容、字符级起止位置
• 拿到匹配位置后，用二分查找快速定位该位置所属的原列表元素索引，同时可直接通过位置比对判断匹配是否完整覆盖整个token，无需额外做字符串等值判断

完整实现代码 #

import re
from bisect import bisect_right

def regex_search_with_token_index(input_list: list[str], pattern: str | re.Pattern) -> list[list]:
    # 构建每个token的起始偏移量表
    token_start_offsets = []
    current_offset = 0
    for token in input_list:
        token_start_offsets.append(current_offset)
        # 累加token长度 + 拼接用的单个空格长度
        current_offset += len(token) + 1
    # 拼接总字符串
    concat_str = " ".join(input_list)
    result = []
    # 单次正则扫描获取所有匹配
    for match in re.finditer(pattern, concat_str):
        match_start_pos = match.start()
        # 二分查找快速定位匹配所属的token索引
        token_idx = bisect_right(token_start_offsets, match_start_pos) - 1
        result.append([token_idx, match.group()])
        
        # 如需判断是否为完整token匹配，启用以下代码即可
        # token_end_pos = token_start_offsets[token_idx] + len(input_list[token_idx])
        # is_full_token_match = (match.start() == token_start_offsets[token_idx]) and (match.end() == token_end_pos)
    return result

# 测试场景验证
if __name__ == "__main__":
    list_a = ["4123", "7648", "afjsdn", "ujaf", "huh23", "n23kl3l24"]
    regex_num = r"\d+"
    matches_with_slno = regex_search_with_token_index(list_a, regex_num)
    print(matches_with_slno)

运行效果与性能说明 #

• 上述测试用例运行输出为[[0, '4123'], [1, '7648'], [4, '23'], [5, '23'], [5, '3'], [5, '24']]，和预期结果完全一致
• 整体时间复杂度和原生单次正则扫描拼接字符串的方案几乎持平：预处理偏移表为O(n)（n为列表长度），每个匹配项的索引用二分查找定位仅需O(log n)，远低于逐元素执行正则的O(n*正则匹配开销)
• 注意事项：拼接用的分隔符必须选择原列表元素中不会出现的字符，避免偏移计算错误；如果更换分隔符，只要把偏移计算时的分隔符长度改成对应值即可。

内容的提问来源于stack exchange，提问作者Suneha K S