Python：查找字符串所有匹配子序列的有序索引的高效算法

问题本质 #

你要解决的是字符串子序列匹配问题：找到字符串a中所有字符顺序和b完全一致、且对应索引严格递增的索引序列。

更优算法思路 #

根据你是要找单个合法解还是所有合法解，分别有两种效率远高于暴力法的方案：

方案1：找单个合法解（贪心算法，时间复杂度O(n)，n为a的长度） #

思路非常简单：从左到右遍历a，每遇到和b当前待匹配位置相同的字符就记录索引，直到b的所有字符都匹配完成，直接返回记录的索引列表即可。

这个方法能保证得到的索引一定是严格递增的，且是字典序最小的合法解。
代码示例（Python）：

def find_one_subsequence(a: str, b: str) -> list[int]:
    res = []
    b_ptr = 0
    len_b = len(b)
    if len_b == 0:
        return res
    for a_idx, char in enumerate(a):
        if char == b[b_ptr]:
            res.append(a_idx)
            b_ptr += 1
            if b_ptr == len_b:
                return res
    return [] # 无匹配时返回空列表

用你给出的示例输入测试，会得到[0, 1, 2, 5, 7, 8]，和你举的合法例子完全一致。

方案2：找所有合法解（预处理+回溯剪枝，时间复杂度远低于暴力枚举） #

暴力法的低效来源于会枚举所有长度为len(b)的递增索引序列再逐一验证，其中大部分序列的字符根本不匹配b。我们可以通过预处理+二分剪枝砍掉所有无效路径：

1. 先预处理a，把每个字符出现的所有索引按升序存在哈希表里
2. 回溯匹配b的每一个字符时，直接在对应字符的预存索引列表里，用二分查找找到第一个大于上一个选中索引的位置，只从这个位置往后遍历可选索引
3. 如果某一步找不到符合要求的索引，直接剪枝不再往下递归
   代码示例（Python）：

import bisect
from collections import defaultdict

def find_all_subsequences(a: str, b: str) -> list[list[int]]:
    # 预处理：存储每个字符对应的升序索引列表
    char_index_map = defaultdict(list)
    for idx, char in enumerate(a):
        char_index_map[char].append(idx)
    
    result = []
    len_b = len(b)
    
    def backtrack(b_pos: int, last_selected_idx: int, path: list[int]):
        # 已经匹配完b的所有字符，存入结果
        if b_pos == len_b:
            result.append(path.copy())
            return
        target_char = b[b_pos]
        # 不存在目标字符直接剪枝
        if target_char not in char_index_map:
            return
        index_list = char_index_map[target_char]
        # 二分找第一个大于上一个选中索引的位置
        start = bisect.bisect_right(index_list, last_selected_idx)
        # 只遍历可选的索引
        for i in range(start, len(index_list)):
            current_idx = index_list[i]
            path.append(current_idx)
            backtrack(b_pos + 1, current_idx, path)
            path.pop()
    
    backtrack(0, -1, [])
    return result

复杂度对比 #

• 暴力法时间复杂度为组合数级别$O(C(n,k))$，其中$n$是a的长度，$k$是b的长度，$n$和$k$稍大就会爆炸
• 预处理+剪枝的方案只会遍历所有合法的匹配路径，每一步查找起始位置的时间复杂度为$O(logm)$，$m$是对应字符的出现次数，效率提升非常明显

内容的提问来源于stack exchange，提问作者Gi Yeon Shin