高效求解压缩字符串子串提取问题的方法探究

针对L、R可达10亿的场景，全量解压必然超时，核心思路是只定位并处理和目标区间重叠的压缩片段，通过预计算长度快速跳过无关部分，全程无需展开整个字符串。

实现步骤 #

1. 预计算每个压缩单元的解压长度 #

先用栈遍历一遍压缩串，记录每个(...)结构的关键信息：

• 遇到(时，先解析前面的重复次数（注意处理多位数字，比如123(ABC)），然后把当前位置、重复次数、初始长度（0）压入栈；
• 遇到)时，弹出栈顶的未闭合单元，计算该单元的总解压长度：内部内容的解压长度 × 重复次数，再把这个长度加到栈顶上层单元（如果存在）的长度中；
• 普通字符直接累加当前所在单元的长度。

遍历完成后，我们能得到整个字符串的总解压长度，以及每个压缩单元的精确长度，为后续定位提供依据。

2. 递归定位目标区间 #

从整个字符串的范围开始，逐步缩小到[L, R]对应的片段：

• 遍历当前处理的字符串片段，分两种情况处理：
  • 普通字符：
    • 若当前字符位置在[L, R]内，直接加入结果；
    • 若当前字符位置超过R，立即停止处理；
    • 若当前字符在L之前，跳过它，同时将L和R各减1（相当于目标区间整体后移一位）。
  • 压缩单元：
    • 先获取该单元的总解压长度total_len和内部内容的解压长度inner_len（total_len / 重复次数）；
    • 若total_len < L：整个单元都在目标区间前，直接跳过，将L和R各减去total_len；
    • 若当前已处理长度 + total_len < L：同样跳过；
    • 否则：目标区间与该单元重叠，无需展开所有重复，直接计算目标位置在单次重复中的偏移：
      • L对应的偏移为(L - 1) % inner_len + 1，R对应的偏移为(R - 1) % inner_len + 1；
      • 递归处理内部内容的[偏移L, 偏移R]区间，得到单次重复中的目标子串；
      • 计算目标区间覆盖的完整重复次数，加上首尾的部分重复片段，拼接后即为最终结果。

实际例子验证 #

例子1：A(BB(CC)) → 解压后ABBCCCCBBCCCC #

假设要取L=5到R=8的子串：

1. 先处理前面的'A'，L和R各减1，变为L=4，R=7；
2. 遇到压缩单元(BB(CC))，总长度为8，内部BB(CC)的长度为8；
3. 进入内部处理BB(CC)：
   • 处理第一个'B'，L=3，R=6；
   • 处理第二个'B'，L=2，R=5；
   • 遇到压缩单元(CC)，总长度4，内部CC长度2，重复次数2；
   • 计算偏移：(2-1)%2+1=2，(5-1)%2+1=1；
   • 递归处理CC的[2,1]，即取第二个'C'再取第一个'C'，加上中间一次完整重复，最终得到CCCC，对应原区间5-8的子串。

例子2：((((((((IMTOOSTRONG)))))))) → 重复8次IMTOOSTRONG #

L=52，R=60：

1. IMTOOSTRONG长度为12，整个串总长度为12×8=96；
2. 计算52的重复偏移：(52-1)%12+1=52-4×12=4，对应IMTOOSTRONG的第4个字符'M'；
3. 60的重复偏移：60-4×12=12，对应第12个字符'N'；
4. 直接取IMTOOSTRONG的第4到第12位，得到MTOOSTRON，与示例结果一致。

避坑点 #

• 务必处理多位数字的重复次数，比如1000000000(ABC)，避免解析错误；
• 递归时注意区间边界，尤其是L和R跨多个重复单元的情况（比如L在第3次重复末尾，R在第5次重复开头）；
• 栈计算长度时，确保嵌套单元的长度累加正确，内层单元长度需计入外层单元。

内容的提问来源于stack exchange，提问作者장승범