迭代插入反向搜索

Question

我有一个代码可以迭代地将自身插入到用户指定的位置。它给出了一个长字符串作为迭代的结果。我需要做的是相反的事情。编写一段代码，接受一个字符串并使用迭代来找出初始字符串是什么以及插入位置。

def iterative_insertion(S, positions):
    R = S

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

    return R

# Example usage
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))

我需要一个函数，它将接受“aaabcdabcdbcdaaabcdabcdbcdabcdabcdabcdbcdabcdabcdabcdabcdbcdabcd”的输入并使用迭代来查找初始字符串和插入位置。

换句话说，输出将是

Inital string = "abcd"
positions = [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

# Example usage
input_string = "aaabcdabcdbcdaaabcdabcdbcdabcdabcdabcdbcdabcdabcdabcdabcdbcdabcd"
initial, insert_positions = reverse_iterative_insertion(input_string)

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

Answer 1

看起来问题只是想找到字符串中存在的模式。

所以这个（或类似的变体）可以工作。

input_string = "aaabcdabcdbcdaaabcdabcdbcdabcdabcdabcdbcdabcdabcdabcdabcdbcdabcd"

pattern = "abcd"

matches = []
start_idx = 0
while True:
    idx = input_string.find(pattern, start_idx)
    if idx == -1:
        break
    matches.append(idx)
    start_idx = idx + 1

print(matches)

返回此（对于给定的示例）：

[2, 6, 15, 19, 26, 30, 34, 41, 45, 49, 53, 60]