基于预计算优化Python算法：批量字符串子序列查询场景

兄弟，我太懂你现在的困境了——原来那个逐个遍历每个S_i去匹配T的方法，在k冲到10亿级的时候，绝对是灾难级的效率。毕竟每次检查都要扫一遍T，10亿次下来，时间成本直接上天。既然提示说要反转逻辑，那咱就换个思路：别让每个子串去凑T，而是先把T的信息提前预处理好，让每个子串快速查档就行。

核心思路：预处理T的字符位置映射 #

咱先把T拆解成一个「字符→出现位置列表」的字典，这个列表是按索引递增排序的（因为T是固定的，所以遍历一遍就能生成）。举个例子，如果T = "abcab"，那这个字典就是：

a: [0, 3], b: [1, 4], c: [2]

这样做的好处是，后面检查每个S_i的时候，不用再扫整个T，而是用二分查找快速定位下一个匹配的位置。

预处理代码示例（Python） #

from collections import defaultdict
import bisect

def preprocess_target(T):
    char_pos_map = defaultdict(list)
    len_T = len(T)
    for idx, char in enumerate(T):
        char_pos_map[char].append(idx)
    return char_pos_map, len_T

这个预处理只需要跑一次，时间复杂度是O(len(T))，完全可以接受。

快速检查单个S_i的逻辑 #

拿到预处理好的映射后，检查每个子串的步骤就很简单了：

1. 初始化一个last_match_pos变量，记录上一个匹配字符在T中的位置，初始值为-1（表示还没开始匹配）。
2. 先剪枝：如果S_i的长度比T长，直接返回False（子序列不可能比原串长）。
3. 遍历S_i的每个字符：
   • 如果字符不在映射里，直接返回False（T里根本没有这个字符，不可能是子序列）。
   • 用二分查找，在该字符的位置列表里找第一个大于last_match_pos的索引（因为子序列要求字符顺序一致，所以下一个字符的位置必须比上一个晚）。
   • 如果找不到这样的索引（比如所有位置都比last_match_pos小），返回False。
   • 更新last_match_pos为找到的位置，继续下一个字符。
4. 遍历完所有字符后，返回True。

检查代码示例（Python） #

def is_subsequence_fast(s, char_pos_map, len_T):
    if len(s) > len_T:
        return False
    last_match_pos = -1
    for char in s:
        if char not in char_pos_map:
            return False
        pos_list = char_pos_map[char]
        # bisect_left找第一个大于last_match_pos的位置
        target_idx = bisect.bisect_left(pos_list, last_match_pos + 1)
        if target_idx >= len(pos_list):
            return False
        last_match_pos = pos_list[target_idx]
    return True

为什么这个方案适合十亿级请求？ #

• 预处理只做一次，成本极低，后续所有请求都能复用这个结果。
• 每个S_i的检查时间是O(len(s) * log M)，其中M是该字符在T中的出现次数。对比原来的O(len(T))每次检查，这个效率提升是数量级的——尤其是当len(T)很大，而len(s)比较小时，差距更明显。
• 预处理后的映射可以直接存在内存里，每个请求过来直接查，不需要重复计算。

额外优化小技巧 #

• 如果你的场景里有大量重复的S_i，可以加个LRU缓存，重复请求直接返回结果，进一步降低计算成本。
• 对于字符集固定的场景（比如仅小写字母），可以用数组代替字典，访问速度会更快。

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