本文介绍一种实用算法，用于在由多个字符串片段组成的 List 中查找连续子串（如 [{"searched_placeholder"}]）所跨越的实际列表索引范围，并返回其起始和结束位置。方法基于拼接模拟与边界回溯，兼顾可读性与正确性。
本文介绍一种实用算法，用于在由多个字符串片段组成的 list 中查找连续子串（如 `[{"searched_placeholder"}]`）所跨越的实际列表索引范围，并返回其起始和结束位置。方法基于拼接模拟与边界回溯，兼顾可读性与正确性。
在实际开发中，我们有时会将一个逻辑上的完整字符串按流式处理、网络分片或模板渲染等需求，拆分为 List<string></string> 存储（例如富文本分段、模板占位符跨块等场景）。此时若需搜索某个跨多个元素的子串（如 "searched_placeholder" 出现在 "[{searched" 和 "_placeholder}] 两个相邻元素中），直接使用 List.contains() 或逐元素匹配将失效——因为目标子串并不完整存在于任一单独元素内。
解决该问题的核心思路是：模拟全局字符串拼接过程，动态追踪子串首次出现时覆盖的最小索引区间。以下为推荐实现方案（经优化与健壮性增强）：
✅ 推荐算法步骤
-
前向扫描：顺序拼接列表元素，一旦拼接结果中首次包含目标子串，记录当前索引为
endIndex； -
反向收缩：从
0到endIndex迭代，逐步移除开头元素内容，直到拼接体不再包含目标子串——此时上一轮索引即为startIndex； -
边界校验：确保
startIndex ≤ endIndex，且子串确实横跨该区间（非完全落在单个元素内）。
? 完整可运行示例（Java）
import java.util.*;
public class FragmentedStringSearch {
public static int[] findSpanningIndices(List<String> fragments, String target) {
if (fragments == null || target == null) {
return new int[]{-1, -1};
}
StringBuilder sb = new StringBuilder();
int endIndex = -1;
// Step 1: Find the smallest index where target appears in cumulative concatenation
for (int i = 0; i < fragments.size(); i++) {
sb.append(fragments.get(i));
if (sb.indexOf(target) >= 0) {
endIndex = i;
break;
}
}
if (endIndex == -1) return new int[]{-1, -1}; // Not found
// Step 2: Backtrack to find minimal starting index
StringBuilder temp = new StringBuilder(sb.toString());
int startIndex = 0;
for (int i = 0; i <= endIndex; i++) {
String prefix = fragments.get(i);
// Remove prefix from temp (simulate dropping element i)
if (temp.length() >= prefix.length() &&
temp.substring(0, prefix.length()).equals(prefix)) {
temp.delete(0, prefix.length());
} else {
break; // Inconsistent state — fallback
}
if (temp.indexOf(target) == -1) {
startIndex = i + 1; // Last element that *must* be included
break;
}
}
return new int[]{startIndex, endIndex};
}
// 测试用例
public static void main(String[] args) {
List<String> str = new ArrayList<>();
str.add("This is a ");
str.add("[{searched");
str.add("_placeholder}]");
str.add(" in this string.");
int[] span = findSpanningIndices(str, "searched_placeholder");
System.out.printf("Start index: %d, End index: %d%n", span[0], span[1]);
// 输出：Start index: 1, End index: 2
}
}⚠️ 注意事项与进阶建议
- 性能考量：该算法时间复杂度为 O(n·m)（n 为列表长度，m 为平均字符串长度），适用于中小规模数据；若需高频查询，建议预构建“全局偏移映射表”（记录每个 fragment 起始全局字符偏移），再通过二分定位边界。
-
边界情况处理：
- 目标子串完全位于单个元素内 →
startIndex == endIndex - 子串跨越三个及以上元素 → 算法仍适用（
endIndex取最后包含位置，startIndex为最早必需位置） - 空元素或
null片段 → 需在调用前清洗数据或增强空值判断
- 目标子串完全位于单个元素内 →
-
正则支持扩展：若需匹配模式（如
\[\{.*?\}\]），可将indexOf替换为Pattern.compile(...).matcher(sb).find()，并同步调整起止索引计算逻辑。
此方案不依赖外部库，逻辑清晰、易于调试，是处理分段字符串精确定位问题的可靠基础解法。
