迭代插入逆搜索：从结果字符串还原初始串与插入位置

问题说明 #

已知iterative_insertion函数可将初始字符串按指定位置迭代插入自身，生成更长的字符串。现需要实现逆操作函数：输入最终生成的长字符串，还原出初始字符串及对应的插入位置列表。

原迭代插入函数代码 #

def iterative_insertion(S, positions):
    R = S

    for pos in positions:
        if 0 <= pos <= len(R):
            R = R[:pos] + R + R[pos:]

    return R

# 示例用法
S = "abcd"
positions = [0, 1, 1, 13]
result = iterative_insertion(S, positions)
expected = "aaabcdabcdbcdaaabcdabcdbcdabcdabcdabcdbcdabcdabcdabcdabcdbcdabcd"

print("Expected: ", expected)
print("Result: ", result)
print("Match: ", result == expected)
print("Lengths: ", len(result), len(S), len(expected))

目标需求 #

输入上述示例中的expected字符串，需还原得到：

初始字符串 = "abcd"
插入位置 = [0, 1, 1, 13]

用户尝试的逆函数代码及问题分析 #

用户实现代码 #

def reverse_iterative_insertion(s):
    initial_string = ""
    positions = []
    current_position = 0

    for char in s:
        if char not in initial_string:
            initial_string += char
        else:
            current_position = initial_string.index(char)
            positions.append(current_position)
            initial_string = initial_string[:current_position] + char + initial_string[current_position:]

    return initial_string, positions

# 示例用法
input_string = "aaabcdabcdbcdaaabcdabcdbcdabcdabcdabcdbcdabcdabcdabcdabcdbcdabcd"
initial, insert_positions = reverse_iterative_insertion(input_string)

print("Initial string:", initial)
print("Insertion positions:", insert_positions)

问题分析 #

该代码逻辑完全不符合原迭代插入操作的逆过程：

• 原操作是将当前整个字符串插入到自身指定位置，每次操作后字符串长度翻倍；而用户代码基于单个字符的存在性构建初始串，完全忽略了原操作的整体插入特性。
• 运行该代码会得到错误结果，无法还原出正确的初始字符串和插入位置列表。

正确的逆操作实现 #

核心思路 #

原操作每次将字符串T插入自身的pos位置，得到R = T[:pos] + T + T[pos:]，此时len(R) = 2 * len(T)。逆操作需反向推导：

1. 从最终字符串开始，每次将当前长度减半（原操作每次长度翻倍），直到无法再减半（得到初始字符串长度）。
2. 对于当前字符串R（长度2L），找到合法的pos（0<=pos<=L），使得R[pos:L+pos]等于R[:pos] + R[L+pos:]（该子串对应上一步的字符串T）。
3. 记录该pos，将T作为当前字符串继续反向推导，最后反转记录的pos列表得到原插入顺序。

实现代码 #

def reverse_iterative_insertion(s):
    current = s
    positions = []
    
    # 逆操作直到长度无法被2整除，或找不到合法插入位置
    while len(current) % 2 == 0:
        L = len(current) // 2
        found_pos = -1
        # 遍历所有可能的插入位置，验证是否符合原操作逻辑
        for pos in range(L + 1):
            T = current[:pos] + current[L+pos:]
            if current == T[:pos] + T + T[pos:]:
                found_pos = pos
                break
        if found_pos == -1:
            break
        positions.append(found_pos)
        current = T
    
    # 反转位置列表，还原原插入顺序
    return current, positions[::-1]

# 示例用法
input_string = "aaabcdabcdbcdaaabcdabcdbcdabcdabcdabcdbcdabcdabcdabcdabcdbcdabcd"
initial, insert_positions = reverse_iterative_insertion(input_string)

print("初始字符串:", initial)
print("插入位置:", insert_positions)

运行验证 #

运行上述代码后，输出结果与目标需求完全一致：

初始字符串: abcd
插入位置: [0, 1, 1, 13]

优化说明 #

• 上述实现通过验证原操作的生成逻辑确保正确性，若需提升效率，可利用原操作的字符串结构特性（R的前pos字符与T的前pos字符一致、R的后L-pos字符与T的后L-pos字符一致）减少验证计算，避免全字符串拼接对比。

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