如何基于子串配对列表对齐两字符串的偏移？重复子串场景下的最优方法探讨

假设我们遇到这样的需求：给定两个字符串 a、b，以及一个子串配对列表 c，需要为每一对子串找到它们在原字符串中的起始和结束偏移，最终生成包含这些信息的新列表。

比如给定以下输入：

a = "how are you ?"
b = "wie gehst's es dir?"

c = [
 ("how", "wie"), 
 ("are", "gehst's"),
 ("you", "es")
]

我们需要得到这样的输出结果：

offsets = [
 ("how", "wie", (0, 3), (0, 3)), 
 ("are", "gehst's", (4, 6), (4, 11)),
 ("you", "es", (7, 9), (12, 14))
]

基础实现思路（适用于无重复子串场景） #

ChatGPT 给出了一个直观的基础实现，核心逻辑就是针对每一对子串，分别在原字符串中查找它们的位置。具体步骤如下：

• 遍历 c 中的每一对子串
• 找到该子串在 a 中的起始和结束索引
• 找到该子串在 b 中的起始和结束索引
• 将子串对与对应的位置信息组合后存入结果列表

对应的代码实现：

a = "how are you ?"
b = "wie gehst's es dir?"
c = [
    ("how", "wie"),
    ("are", "gehst's"),
    ("you", "es")
]

# Create the offsets list
offsets = []
for substring_a, substring_b in c:
    # Find the start and end indices for substring_a in string a
    start_a = a.find(substring_a)
    end_a = start_a + len(substring_a) - 1
    
    # Find the start and end indices for substring_b in string b
    start_b = b.find(substring_b)
    end_b = start_b + len(substring_b) - 1
    
    # Append the result as a tuple
    offsets.append((substring_a, substring_b, (start_a, end_a), (start_b, end_b)))

# Output the result
print(offsets)

问题：重复子串场景下的局限性 #

上面的方法在子串重复出现的场景下就会失效，比如下面的例子：

a = "how are you ? are you okay ?"
b = "wie gehst's es dir?  geht es dir gut "

c = [
 ("how", "wie"), 
 ("are", "gehst's"),
 ("you", "es"),
 ("are", "geht"), 
 ("you", "es"),
 ("okay", "gut")
]

这里 a 中的 "are" 和 "you" 各出现了两次，b 中的 "es" 也出现了两次，用 find() 只能拿到第一个匹配的位置，无法对应 c 列表中顺序对应的那一个子串的位置。

更优实现：跟踪查找位置解决重复问题 #

解决重复子串问题的核心思路是跟踪当前的查找位置，而不是每次都从字符串开头查找。具体来说：

• 为字符串 a 和 b 分别维护一个当前的查找起始位置，初始值为 0
• 遍历 c 中的每一对子串时，从当前的起始位置开始查找对应的子串
• 找到位置后，更新下一次的查找起始位置为当前匹配的结束位置之后，避免重复匹配前面的子串

对应的优化代码：

a = "how are you ? are you okay ?"
b = "wie gehst's es dir?  geht es dir gut "

c = [
 ("how", "wie"), 
 ("are", "gehst's"),
 ("you", "es"),
 ("are", "geht"), 
 ("you", "es"),
 ("okay", "gut")
]

offsets = []
# 维护当前的查找起始位置，避免重复匹配前面的子串
current_pos_a = 0
current_pos_b = 0

for sub_a, sub_b in c:
    # 从current_pos_a开始查找sub_a在a中的位置
    start_a = a.find(sub_a, current_pos_a)
    if start_a == -1:
        # 处理找不到子串的情况，可根据需求调整错误逻辑
        raise ValueError(f"Substring '{sub_a}' not found in a starting from position {current_pos_a}")
    end_a = start_a + len(sub_a) - 1
    # 更新下一次的查找起始位置
    current_pos_a = end_a + 1
    
    # 同理处理b中的子串
    start_b = b.find(sub_b, current_pos_b)
    if start_b == -1:
        raise ValueError(f"Substring '{sub_b}' not found in b starting from position {current_pos_b}")
    end_b = start_b + len(sub_b) - 1
    current_pos_b = end_b + 1
    
    offsets.append((sub_a, sub_b, (start_a, end_a), (start_b, end_b)))

print(offsets)

这个优化方案的优势：

1. 完美解决了重复子串的匹配问题，能够精准对应 c 列表顺序中的目标子串
2. 性能更高效，无需每次从字符串开头遍历，而是从上一次匹配的结束位置开始查找
3. 加入了异常处理，鲁棒性更强，可根据实际需求调整错误处理逻辑

如果需要支持更复杂的匹配规则（比如大小写忽略、非精确匹配等），可以把 find() 替换为正则表达式的 search() 方法，并传入 pos 参数指定起始位置，核心思路依然是跟踪当前的查找位置。

备注：内容来源于stack exchange，提问作者alvas