从插入代码中获取正确的输出匹配

Question

我无法让 iter_position_reverse 中的测试用例字符串通过。我不确定我必须改变什么才能解决这个问题

这是 iterative_insertion 代码：

def iterrative_insertion(S, positions):
    R = S
    offset = 0
    for pos in positions:
        R = R[:pos + offset] + S + R[pos + offset:]
        offset + len(S)
    return R

# Example usage
S = "abcdabd"
positions = [0, 1, 16]
result = iterrative_insertion(S, positions)
expected = 'aabcdabdbcdabdababcdabdcdabd'
print(expected)
print(result)
print(result == expected)
print(len(result),len(S), len(expected))

# abcdabd
# abcdabdabcdabd
# aabcdabdbcdabdabcdabd
# aabcdabdbcdabdababcdabdcdabd

这是我的 iter_position_reverse 代码：

import iterrative_insertion
def iter_position_reverse(R):
    # Initialize variables to store S and positions
    S = ""
    positions = []

    # Start iterating through R
    i = 0
    while i < len(R):
        # Find the longest substring that matches the beginning of R
        j = 0
        while j < len(S) and i + j < len(R) and S[j] == R[i + j]:
            j += 1

        # If we found a match, add its position to the positions list
        if j == len(S):
            positions.append(i)

        # If we didn't find a match, add the next character to S
        S += R[i]

        # Move to the next character in R
        i += 1

    return S, positions

# Test cases
test_strings = [
    "abcdabdaabcdabdbcdabdabcdabd",
    "aabcdabdbcdabdabcdabdabcdabd",
    "aababababcdabdcdabdcabcdabddabdcdabdbcdabd",
    "aaaaaaababababcdabdcdabdcabcdabddabdcdabdbcdabdababababcdabdcdabdcabcdabddabdcdabdbcdabdababababcdabdcdabdcabcdabddabdcdabdbcdabdbabababcdabdcdabdcabcdabddabdcdabdbcdabdababababcdabdcdabdcabcdabddabdcdabdbcdabd",
    "ddodoremefasolasiremefasolasioremdoredoremefasolasimefasolasiefasolasi",
    "abdaabcdabdbcdabdb"
]



for R in test_strings:
    S, positions = iter_position_reverse(R)
    print("Input String:", R)
    print("S:", S)
    print("Positions:", positions)
    print()
    if iterrative_insertion.iterrative_insertion(S,positions) == R:
        print("We did it.")
else:
    print(f"It did not work for {R}")

代码输出没有给出是否是“我们做到了”的答案。或“它对 {R} 不起作用”。

代码尝试查找并重建输入字符串中与输入字符串开头匹配的子字符串，并存储这些匹配的位置。然后，它检查重建的字符串在由 iterative_insertion 函数处理时是否可以生成原始输入字符串。主要目标是测试和验证 iter_position_reverse 中实现的字符串匹配和重建算法。

Answer 1

这里的技巧是在原始字符串的长度范围内使用指针，指针将比较起始字符的扩展列表和该扩展集之后的字符。如果这些列表匹配，那么我们将保存一对候选字符串。有很多机会可以优化它，例如，一旦你到达一半，继续寻找就没有意义，但我会把它留给你：

注意，我已经更改了您的测试数据，以便更轻松地查看测试用例，但请随意重用您的实际测试数据。

def iter_position_reverse(original_string):
    starting_string = ""
    remaining_string = ""
    for pointer in range(len(original_string)):
        if original_string[0:pointer] == original_string[pointer: 2*pointer]:
            starting_string = original_string[0:pointer]
            remaining_string = original_string[pointer:]

    if starting_string + remaining_string == original_string:
        return f"We did it: \"{starting_string}\" + \"{remaining_string}\" --> \"{original_string}\""
    else:
        return f"It did not work for \"{original_string}\""

然后你可以测试：

## -------------------
# Test cases
## -------------------
test_strings = [
    "abcd",         ## no matching initial sub-string
    "aabc",         ## "a" and "abc" reconstructs "aabc"
    "abab",         ## "ab" and "ab" reconstructs "abab"
    "foofoobar",    ## "foo" and "foobar" reconstructs "foofoobar"
]

for test_string in test_strings:
    result = iter_position_reverse(test_string)
    print(result)
## -------------------

这会给你：

We did it: "" + "abcd" --> "abcd"
We did it: "a" + "abc" --> "aabc"
We did it: "ab" + "ab" --> "abab"
We did it: "foo" + "foobar" --> "foofoobar"

请注意，我构建此答案是为了专门解决：需要帮助让迭代位置反向测试用例通过，该问题已作为此问题的重复项关闭，因此我假设它本质上是相同的任务。