如何高效实现按字符串向量分割字符串并保留分隔符？

明确需求：给定输入字符串和一组分隔符，将字符串拆分为非分隔符文本块与匹配到的分隔符交替组成的列表，例如输入"AB<sep1>DE<sep1><sep2>"（分隔符为<sep1>、<sep2>），输出列表为["AB", "<sep1>", "DE", "<sep1>", "<sep2>"]。

核心高效方案：多模式匹配算法（AC自动机） #

如果分隔符数量较多（比如超过10个），逐个遍历分隔符去字符串中匹配的效率会很低（时间复杂度O(N*M)，N是字符串长度，M是分隔符总数）。而AC自动机可以将时间复杂度降到O(N + L)（L是所有分隔符的总长度），非常适合这类多分隔符的匹配场景。

具体实现步骤 #

1. 构建AC自动机：

   • 将所有分隔符作为模式串，构建AC自动机的前缀树与失败指针，同时为每个模式串记录其长度和内容，方便匹配时快速定位。
   • 若存在长度重叠的分隔符（比如<sep>和<sep1>），需保证匹配时优先识别更长的分隔符，构建时可通过排序或节点权重设置实现。

2. 遍历字符串完成拆分：

   • 维护current_pos变量，记录当前未处理的字符串起始位置。
   • 用AC自动机扫描字符串，每当匹配到分隔符：
     • 若current_pos到分隔符起始位置间有非空文本，将这段文本加入结果列表。
     • 将匹配到的分隔符加入结果列表。
     • 更新current_pos为分隔符结束的位置。
   • 扫描结束后，若current_pos小于字符串长度，将剩余文本加入结果列表。

简化实现（分隔符数量少的场景） #

如果分隔符数量极少（仅几个），可以用双指针+字符串查找的方式快速实现，虽然效率不如AC自动机，但代码简洁：

• 每次从当前位置开始，查找所有分隔符在当前位置后的首次出现位置，取最早出现的那个。
• 根据该位置拆分文本块与分隔符，重复操作直到遍历结束。

示例伪代码 #

def split_with_separators(s, separators):
    # 按分隔符长度降序排序，优先匹配长分隔符
    sorted_seps = sorted(separators, key=lambda x: len(x), reverse=True)
    sep_length = {sep: len(sep) for sep in sorted_seps}
    result = []
    current_idx = 0
    str_len = len(s)
    
    while current_idx < str_len:
        min_match_pos = str_len
        matched_sep = None
        # 查找当前位置最早出现的分隔符
        for sep in sorted_seps:
            pos = s.find(sep, current_idx)
            if pos != -1 and pos < min_match_pos:
                min_match_pos = pos
                matched_sep = sep
        
        if matched_sep:
            # 加入非分隔符文本块
            if current_idx < min_match_pos:
                result.append(s[current_idx:min_match_pos])
            # 加入匹配到的分隔符
            result.append(matched_sep)
            current_idx = min_match_pos + sep_length[matched_sep]
        else:
            # 无匹配分隔符，加入剩余文本
            result.append(s[current_idx:])
            break
    return result

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